CF446E.DZY Loves Bridges

DZY owns 2_m_ islands near his home, numbered from 1 to 2_m_. He loves building bridges to connect the islands. Every bridge he builds takes one day's time to walk across.

DZY has a strange rule of building the bridges. For every pair of islands u, v (u ≠ v), he has built 2_k_ different bridges connecting them, where (a|b means b is divisible by a). These bridges are bidirectional.

Also, DZY has built some bridges connecting his home with the islands. Specifically, there are a__i different bridges from his home to the i-th island. These are one-way bridges, so after he leaves his home he will never come back.

DZY decides to go to the islands for sightseeing. At first he is at home. He chooses and walks across one of the bridges connecting with his home, and arrives at some island. After that, he will spend t day(s) on the islands. Each day, he can choose to stay and rest, or to walk to another island across the bridge. It is allowed to stay at an island for more than one day. It's also allowed to cross one bridge more than once.

Suppose that right after the t-th day DZY stands at the i-th island. Let ans[i] be the number of ways for DZY to reach the i-th island after t-th day. Your task is to calculate ans[i] for each i modulo 1051131.

DZY 在他家附近拥有 $2^m$ 座岛屿，编号从 $1$ 到 $2^m$。他热衷于建造桥梁来连接这些岛屿。每座桥需要花费一天时间才能穿越。

DZY 建造桥梁遵循一条奇特的规则：对任意一对岛屿 $u,\,v$（其中 $u \ne v$），他建造了 $2^k$ 座不同的桥来连接它们，其中

（$a\mid b$ 表示 $a$ 整除 $b$）。这些桥是双向的。

此外，DZY 还建造了一些从他家通往各岛屿的桥。具体而言，从他家到第 $i$ 座岛屿共有 $a_i$ 座不同的桥。这些桥为单向桥，因此一旦他离开家，便无法再返回。

DZY 决定前往这些岛屿观光。初始时，他位于家中。他选择并穿越一座连接家与某岛屿的桥，抵达某座岛屿。之后，他将在岛屿上停留 $t$ 天。每天，他可以选择留在当前岛屿休息，或通过一座桥前往另一座岛屿。允许他在同一座岛屿上停留多天，也允许多次穿越同一座桥。

假设在第 $t$ 天结束时，DZY 正好位于第 $i$ 座岛屿上。令 $ans[i]$ 表示 DZY 在第 $t$ 天结束时恰好位于第 $i$ 座岛屿的方案数。你的任务是，对每个 $i$，计算 $ans[i]$ 对 $1051131$ 取模的结果。

To avoid huge input, we use the following way to generate the array a. You are given the first s elements of array: _a_1, a_2, ..., a__s. All the other elements should be calculated by formula: a__i = (101·a__i - s + 10007) mod 1051131 (s < i ≤ 2_m).

The first line contains three integers m, t, s (1 ≤ m ≤ 25; 1 ≤ t ≤ 1018; 1 ≤ s ≤ min(2_m_, 105)).

The second line contains s integers _a_1, _a_2, ..., a__s (1 ≤ a__i ≤ 106).

为避免输入过大，我们采用以下方式生成数组 $a$。你将得到数组的前 $s$ 个元素：$a_1,\,a_2,\,\dots,\,a_s$。其余所有元素需按如下公式计算：$a_i = (101 \cdot a_{i-s} + 10007) \bmod 1051131$（其中 $s < i \leq 2^m$）。

第一行包含三个整数 $m,\,t,\,s$（$1 \leq m \leq 25$；$1 \leq t \leq 10^{18}$；$1 \leq s \leq \min(2^m,\,105)$）。

第二行包含 $s$ 个整数 $a_1,\,a_2,\,\dots,\,a_s$（$1 \leq a_i \leq 10^6$）。

To avoid huge output, you only need to output xor-sum of all the answers for all i modulo 1051131 (1 ≤ i ≤ 2_m_), i.e. (ans[1] mod 1051131) xor (ans[2] mod 1051131) xor... xor (ans[n] mod 1051131).

为避免输出过大，你只需输出所有 $i$（$1 \le i \le 2^m$）对应的答案的异或和（模 $1051131$），即

$$(\text{ans}[1] \bmod 1051131) \oplus (\text{ans}[2] \bmod 1051131) \oplus \dots \oplus (\text{ans}[n] \bmod 1051131).$$

In the first sample, ans = [6, 7, 6, 6].

If he wants to be at island 1 after one day, he has 6 different ways:

1. home —> 1 -(stay)-> 1
2. home —> 2 —> 1
3. home —> 3 —> 1
4. home —> 3 —> 1 (note that there are two different bridges between 1 and 3)
5. home —> 4 —> 1
6. home —> 4 —> 1 (note that there are two different bridges from home to 4)

In the second sample, (_a_1, _a_2, _a_3, _a_4, _a_5, _a_6, _a_7, _a_8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849), ans = [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335].

在第一个样例中，ans = [6, 7, 6, 6]。

若他希望一天后位于岛屿 1，则共有 6 种不同的路径：

1. 家 → 1 →（停留）→ 1
2. 家 → 2 → 1
3. 家 → 3 → 1
4. 家 → 3 → 1（注意：岛屿 1 与 3 之间有两座不同的桥）
5. 家 → 4 → 1
6. 家 → 4 → 1（注意：从家到岛屿 4 有两座不同的桥）

在第二个样例中，(a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849)，ans = [235771, 712729, 433182, 745954, 139255, 935785, 620229, 644335]。