| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 512 MB | 11 | 2 | 1 | 50.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)$.
3 2 1 2 3
12
2 1000000000 1 2
140625003