컨볼루션

집합 $U = \{0, 1, 2, \dots, n-1\}$의 모든 부분집합을 생각하자. 부분집합 $A = \{a_1, a_2, \dots, a_k\}$마다 정수 $p(A) = \sum_{i=1}^k 2^{a_i}$가 하나씩 대응한다. $n$개의 원소로 이루어진 집합 위의 함수 $F$는 길이가 $2^n$인 정수 배열 $f$로 정해지며, $F(A) = f[p(A)]$이다.

두 함수 $F$와 $G$가 주어진다. 다음 식을 만족하는 함수 $H$를 구하라.

$H(A) = \sum_{B \cup C = A} F(B)G(C).$

첫 줄에 두 정수 $n$과 $t$가 주어진다 ($1 \le n \le 16$, $1 \le t \le 100$). $n$은 집합 $U$의 크기이고, $t$는 테스트 케이스의 개수이다.

둘째 줄에는 두 정수 $a$와 $b$가 주어진다. 둘 다 1 이상 $10^9$ 이하이다. 이 값은 다음 의사 난수 생성기에 쓰인다.

1. unsigned int cur = 0; // unsigned 32-bit integer
2. unsigned int nextRand16() {
3.   cur = cur * a + b; // calculated modulo 2^32
4.   return cur / 2^16; // integer from 0 to 2^16-1
5. }

테스트 케이스는 순서대로 생성된다. 각 테스트 케이스에서는 먼저 배열 $f$의 원소를 인덱스가 증가하는 순서로 만들고, 같은 순서로 배열 $g$의 원소를 만든다. 각 원소는 nextRand16()을 호출해 얻는다.

각 테스트 케이스마다 $\left(\sum_A H(A) \cdot (p(A)+1)\right) \bmod 2^{32}$의 값을 한 줄에 정수 하나로 출력한다.

첫 번째 예제의 배열은 다음과 같다.

• $f_1$: 3, 113, 3395, 36331, 41370, 61471, 9130, 11774
• $g_1$: 25547, 45526, 55066, 13590, 14501, 41817, 9356, 18543
• $h_1$: 76641, 8167827, 273846333, 5284992017, 1656829263, 11450721456, 3699971823, 14260048942
• $f_2$: 32024, 43238, 51978, 52034, 53714, 38578, 43250, 52338
• $g_2$: 62834, 50034, 59250, 8050, 44914, 36722, 53106, 20338
• $h_2$: 2012196016, 6482475400, 8243104152, 15561662464, 7225902008, 16869349792, 22350138288, 44342816072