题目描述

黑板上写着$N$个非负整数：$A_1, ..., A_N$。

Snuke可以按任意顺序，最多总共进行$K$次操作：

• 操作A：将黑板上的每个整数$X$替换为$X$除以$2$，向下取整得到的整数。
• 操作B：将黑板上的每个整数$X$替换为$X$减去$1$。如果黑板上有一个或多个$0$，则不能执行此操作。

求Snuke执行操作后，在黑板上可能出现的不同整数组合的数量，对$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$

输出

输出Snuke执行操作后，在黑板上可能出现的不同整数组合的数量，对$1,000,000,007$取模后的结果。

示例输入1

2 2
5 7

示例输出1

6

黑板上可能的整数组合有六种：$(1, 1)$, $(1, 2)$, $(2, 3)$, $(3, 5)$, $(4, 6)$和$(5, 7)$。例如，$(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