Problem Description

Given an integer sequence of length $N$, $A_1, A_2, ..., A_N$, perform the following operation exactly $K$ times:

• Choose an index $i$ ($1 \leq i \leq N$). Divide $A_i$ by $2$, rounding down to the nearest integer.

Find the number of possible sequences after $K$ operations, modulo $10^9 + 7$.

Input Format

The input is given from the standard input in the following format:

$N$ $K$ $A_1$ $A_2$ $...$ $A_N$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 2
0 3 4

Sample Output #1

6

Sample Input #2

3 100
1 1 1

Sample Output #2

7

Sample Input #3

5 7
10 12 15 20 30

Sample Output #3

330

Sample Input #4

7 1000000000
100261694256177806 55017793609323647 50568971510512136 98912633370372323 51937770757669401 50688484559490819 108712166294779912

Sample Output #4

322647718

Notes/Hints

Constraints

• $1 \leq N \leq 50$
• $0 \leq A_i \leq 10^{18}$ ($1 \leq i \leq N$)
• $0 \leq K \leq 10^9$
• All input values are integers.

Sample Explanation 1

Initially, the sequence $A$ is $A = [0, 3, 4]$. Possible sequences after $K = 2$ operations include $[0, 3, 4]$ and $[0, 1, 2]$. The sequence $[0, 3, 4]$ can be achieved as follows:
- Choose $i = 1$. The sequence remains $[0, 3, 4]$.
- Choose $i = 1$. The sequence remains $[0, 3, 4]$.

The sequence $[0, 1, 2]$ can be achieved, for example, as follows:
- Choose $i = 2$. The sequence becomes $[0, 1, 4]$.
- Choose $i = 3$. The sequence becomes $[0, 1, 2]$.

见题面 Input 部分

见题面 Output 部分