Problem1930--2048

1930: 2048

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

TC喜欢2048,甚至想出了一款游戏。  

有n个网格排列在一行,在游戏开始时,一些网格已经被填充了2或4 

首先,你需要用2或4填充空的网格,若两个数相邻且相等即可将它们相加合并。 

最终目标是使得最大的数字大于等于2k。 

现在,给你游戏的初始状态,空的网格用0表示。请你来帮TC计算出有多少种方案,使得网格中最大的数字大于等于2k。 

Input

第一行包含两个整数 n, k. (n<=2000,k<=11)  
第二行包含n个整数 a1,a2,…,an(ai = 0, 2, 4). 

Output

输出一个整数表示答案, 由于答案可能很大, 请对 109+7取模.

Sample Input Copy

5 4 
2 0 0 4 4

Sample Output Copy

2