問題文

黒板に $N$ 個の非負整数 $A_1, ..., A_N$ が書かれています．

すぬけ君は，次のいずれかの操作を，好きな順番で，合わせて $K$ 回まで行うことができます．

• 操作 A: 黒板に書かれている整数すべてを，$2$ で割って小数点以下を切り捨てたものに置き換える．
• 操作 B: 黒板に書かれている整数すべてを，$1$ を引いたものに置き換える．ただし，黒板に $0$ が一つでも書かれている場合はこの操作を行うことができない．

すぬけ君が操作を行った後の黒板上の整数の書かれ方として，異なるものは何通りあるかを $mod 1,000,000,007$ で求めてください．

制約

• $1 \\leq N \\leq 200$
• $1 \\leq A_i \\leq 10^{18}$
• $1 \\leq K \\leq 10^{18}$
• $A_i, K$ は整数

入力

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

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

出力

すぬけ君が操作を行った後の黒板上の整数の書かれ方として，異なるものは何通りあるかを $mod 1,000,000,007$ で出力せよ．

入力例 1

2 2
5 7

出力例 1

6

黒板上の整数の書かれ方としては，$(1, 1), (1, 2), (2, 3), (3, 5), (4, 6), (5, 7)$ の $6$ 通りがあります． 例えば，$(1, 2)$ は操作 A, 操作 B の順に操作を行うことで得ることができます．

入力例 2

3 4
10 13 22

出力例 2

20

入力例 3

1 100
10

出力例 3

11

入力例 4

10 123456789012345678
228344079825412349 478465001534875275 398048921164061989 329102208281783917 779698519704384319 617456682030809556 561259383338846380 254083246422083141 458181156833851984 502254767369499613

出力例 4

164286011