配点 : $1200$ 点

問題文

黒板に $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$ で出力せよ．

2 2
5 7

6

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

3 4
10 13 22

20

1 100
10

11

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

164286011