問題文

長さ $N$ の整数列 $A_1, A_2, ..., A_N$ が与えられます。 この数列に以下の操作をちょうど $K$ 回施します。

• 添字 $i$ ($1 \\leq i \\leq N$) を一つ選ぶ。$A_i$ を $2$ で割る。ただし商は整数単位で計算し、あまりは切り捨てる。

$K$ 回の操作のあとの数列としてありうるものの個数を $10^9 + 7$ で割ったあまりを求めてください。

制約

• $1 \\leq N \\leq 50$
• $0 \\leq A_i \\leq 10^{18}$ ($1 \\leq i \\leq N$)
• $0 \\leq K \\leq 10^9$
• 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_1$ $A_2$ $...$ $A_N$

出力

答えを出力せよ。

入力例 1

3 2
0 3 4

出力例 1

6

はじめ、数列 $A$ は A = \[0, 3, 4\] です。 $K = 2$ 回の操作のあとの数列としてありうるものとしては、\[0, 3, 4\] や \[0, 1, 2\] などがあります。

数列 \[0, 3, 4\] は以下のようにして実現できます。

• $i = 1$ を選ぶ。数列は \[0, 3, 4\] となる。
• $i = 1$ を選ぶ。数列は \[0, 3, 4\] となる。

また、数列 \[0, 1, 2\] はたとえば以下のようにして実現できます。

• $i = 2$ を選ぶ。数列は \[0, 1, 4\] となる。
• $i = 3$ を選ぶ。数列は \[0, 1, 2\] となる。

入力例 2

3 100
1 1 1

出力例 2

7

入力例 3

5 7
10 12 15 20 30

出力例 3

330

入力例 4

7 1000000000
100261694256177806 55017793609323647 50568971510512136 98912633370372323 51937770757669401 50688484559490819 108712166294779912

出力例 4

322647718