题目描述

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

黑板上现在有 $N$ 个非负整数，第 $i$ 个数字是 $A_i$。

你现在可以以执行最多 $K$ 次操作，两种操作的执行顺序任意：

• 操作 A：将每个数字 $X$ 变成 $\left \lfloor \dfrac{X}{2} \right \rfloor$。
• 操作 B：将每个数字 $X$ 变成 $X-1$。当存在一个数为零时不能执行该操作。

你现在需要算出黑板上数字的所有可能情况数，对 $10^9+7$ 取模。

• $1 \leq N \leq 200$
• $1 \leq A_i \leq 10^{18}$
• $1 \leq K \leq 10^{18}$

2 2
5 7

6

3 4
10 13 22

20

1 100
10

11

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

164286011

提示

制約

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

Sample Explanation 1

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