问题文

给定一个长度为 $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 = [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