分数: 1200 点
问题陈述
有 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