DZY 在他家附近拥有 2m 个岛屿,编号从 1 到 2m。他喜欢建造桥梁来连接岛屿。他建造的每一座桥都需要一天的时间才能走完。
DZY 有一个奇怪的搭建桥梁的规则。对于每对岛屿 u, v (u ≠ v),他建造了 2k 座不同的桥梁连接它们,其中 $$k = \max \left\{ k : 2^k | abs(u - v) \right\}$$ (a|b 表示 b 可以被 a 整除)。这些桥是双向的。
此外,DZY 还建造了一些桥梁连接他的家和岛屿。具体来说,从他的家到第 i 个岛有 ai 座不同的桥梁。这些都是单向桥,所以他离开家后就再也不会回来了。
DZY决定去海岛观光。起初他在家。他选择并走过其中一座连接他家的桥梁,到达了某个岛屿。之后,他将在岛上度过 t 天。每天,他可以选择留下来休息,也可以步行过桥去另一个岛。允许在岛上停留一天以上。还允许多次过一座桥。
假设在第 t 天之后 DZY 就站在第 i 个岛。令 ans[i] 为 DZY 在第 t 天后到达第 i 个岛屿的方式数。你的任务是计算每个 i 模 1051131 的 ans[i]。
输入
为了避免巨大的输入,我们使用以下方式生成数组a。给定数组的前 s 个元素:a1, a2, ..., as。所有其他元素应按以下公式计算:ai = (101·ai - s + 10007) mod 1051131 (s < i ≤ 2m)。
第一行包含三个整数 m、t、s (1 ≤ m ≤ 25; 1 ≤ t ≤ 1018; 1 ≤ s ≤ min(2m, 105))。
第二行包含 s 个整数 a1, a2, ..., as (1 ≤ ai ≤ 106)。
输出
为了避免巨大的输出,您只需输出所有 i 模 1051131 (1 ≤ i ≤ 2m) 的所有答案的异或和,即 (ans[1] mod 1051131) xor (ans[2] mod 1051131) xor...异或(ans[n] mod 1051131)。
示例
输入 #1
2 1 4 1 1 1 2
输出 #1
1
输入 #2
3 5 6 389094 705719 547193 653800 947499 17024
输出 #2
556970
注意
在第一个示例中,ans = [6,7,6,6]。
如果他想在一天后回到 1 号岛,他有 6 种不同的方式:
1. 家 —> 1 -(停留)-> 1
2.首页 —> 2 —> 1
3.首页 —> 3 —> 1
4. home —> 3 —> 1(注意1和3之间有两个不同的桥)
5.首页 —> 4 —> 1
6. home —> 4 —> 1(注意从 home 到 4 有两个不同的桥)
在第二个样本中,(a1, a2, a3, a4, a5, a6, a7, a8) = (389094, 705719, 547193, 653800, 947499, 17024, 416654, 861849), ans = [235771, 712729、433182、745954、139255、935785、620229、644335]。