XOR의 거듭제곱

시간 제한6초메모리 제한512 MB

요약

n개의 정수가 주어질 때, 모든 2^n개 부분집합에 대해 부분집합 원소들의 XOR의 popcount의 k제곱을 합한 값을 1e9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 9점
유형: 비트 연산, 수학, 조합론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Bobo는 $n$ 개의 정수로 이루어진 집합 $\{a_1, a_2, \dots, a_n\}$ 을 가지고 있다. 그는 부분집합 $\{x_1, x_2, \dots, x_m\}$ 을 무작위로 고른다. 모든 부분집합이 같은 확률로 선택된다. 이때 $[\mathrm{popcount}(x_1 \oplus x_2 \oplus \dots \oplus x_m)]^k$ 의 기댓값을 구하려고 한다.

$\mathrm{popcount}(x)$ 는 $x$ 를 이진법으로 나타냈을 때 1의 개수이고, $\oplus$ 는 비트별 배타적 논리합을 뜻한다.

입력

첫째 줄에 정수 $n, k$ 가 주어진다. ( $1 \leq n \leq 44, 1 \leq k \leq 10^9$ )

둘째 줄에 $n$ 개의 정수 $a_1, a_2, \dots, a_n$ 이 주어진다. ( $0 \leq a_i < 2^{44}$ )

출력

기댓값을 $E$ 라 할 때, $E \cdot 2^n \bmod (10^9+7)$ 을 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
3 2
1 2 3
```
예상 출력
```
12
```
예제 2
입력
```
2 1000000000
1 2
```
예상 출력
```
140625003
```