시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 512 MB 0 0 0 0.000%

문제

Bobo has a set of $n$ integers $\{a_1, a_2, \dots, a_n\}$. He randomly picks a subset $\{x_1, x_2, \dots, x_m\}$ (each subset has equal probability to be picked), and would like to know the expectation of $[\mathrm{popcount}(x_1 \oplus x_2 \oplus \dots \oplus x_m)]^k$.

Note that $\mathrm{popcount}(x)$ is the number of ones in the binary notation of $x$, and $\oplus$ denotes bitwise exclusive-or.

입력

The first line contains $2$ integers $n, k$ ($1 \leq n \leq 44, 1 \leq k \leq 10^9$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i < 2^{44}$).

출력

If the expectation is $E$, print a single integer denotes $E \cdot 2^n \bmod (10^9+7)$.

예제 입력 1

3 2
1 2 3

예제 출력 1

12

예제 입력 2

2 1000000000
1 2

예제 출력 2

140625003