← 返回题目列表

AtCoder · arc086_d

F. 移位和减量

中文机器翻译题面 查看原题

分数: 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