← 返回题目列表

AtCoder · code_festival_2018_quala_c

C. 一半

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

配点 : 500 点

問題文

长度为 N 的整数列 A_1, A_2, ..., A_N 。对这个数列正好施行以下操作 K 次。选择一个

  • 添字 i (1 \leq i \leq N)。用A_i 的 2 除,不过商以整数单位计算,余数舍去。求操作

K 次后的数列可能存在的数的个数对 10^9 + 7 取余。起初,数列

制約

  • 1 \leq N \leq 50
  • 0 \leq A_i \leq 10^{18} (1 \leq i \leq N)
  • 0 \leq K \leq 10^9
  • 输入值全为整数。

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 ... A_N

出力

输出答案。


入力例 1

3 2
0 3 4

出力例 1

6

。操作 A 是 A = [0, 3, 4] 。 K = 2 次后的数列可能有[0, 3, 4] 呀 我正在使用 [0, 1, 2] 等。

数列 [0, 3, 4] 可以通过以下方式实现。选择

  • i = 1 。数列变为 [0, 3, 4] 。另外,数列
  • i = 1 。数列变为 [0, 3, 4] 。另外,数列

此外,数列 [0, 1, 2] 例如,可以通过以下方式实现。

  • i = 2 。数列变为 [0, 1, 4] 。另外,数列
  • i = 3 。数列变为 [0, 1, 2] 。另外,数列

入力例 2

3 100
1 1 1

出力例 2

7

入力例 3

5 7
10 12 15 20 30

出力例 3

330

入力例 4

7 1000000000
100261694256177806 55017793609323647 50568971510512136 98912633370372323 51937770757669401 50688484559490819 108712166294779912

出力例 4

322647718