19143번 - Power of XOR 다국어

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)$.