回想一下,二项式系数 $$$\binom{x}{y}$$$ 计算如下($$$x$$$ 和 $$$y$$$ 是非负整数):
- 如果 $$$x < y$$$,则 $$$\binom{x}{y} = 0$$$;
- 否则,$$$\binom{x}{y} = \frac{x!}{y! \cdot (x-y)!}$$$。
给定一个数组 $$$a_1, a_2, \dots, a_n$$$ 和一个整数 $$$k$$$。您必须计算一个新数组 $$$b_1, b_2, \dots, b_n$$$,其中
- $$$b_1 = (\binom{1}{k} \cdot a_1) \bmod 998244353$$$;
- $$$b_2 = (\binom{2}{k} \cdot a_1 + \binom{1}{k} \cdot a_2) \bmod 998244353$$$;
- $$$b_3 = (\binom{3}{k} \cdot a_1 + \binom{2}{k} \cdot a_2 + \binom{1}{k} \cdot a_3) \bmod 998244353$$$,依此类推。
正式来说,$$$b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353$$$。
请注意,数组是以修改后的方式给出的,并且您也必须以修改后的方式输出它。
输入
输入的唯一行包含六个整数 $$$n$$$、$$$a_1$$$、$$$x$$$、$$$y$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n \le 10^7$$$; $$$0 \le a_1, x, y < m$$$; $$$2 \le m \le 998244353$$$; $$$1 \le k \le 5$$$)。
数组 $$$[a_1, a_2, \dots, a_n]$$$ 生成如下:
- $$$a_1$$$ 在输入中给出;
- 对于 $$$2 \le i \le n$$$,$$$a_i = (a_{i-1} \cdot x + y) \bmod m$$$。
输出
由于输出最多 $$$10^7$$$ 整数可能太慢,因此您必须执行以下操作:
让 $$$c_i = b_i \cdot i$$$ (乘法后不取模 $$$998244353$$$)。打印整数 $$$c_1 \oplus c_2 \oplus \dots \oplus c_n$$$,其中 $$$\oplus$$$ 表示按位异或运算符。
示例
输入 #1
5 8 2 3 100 2
输出 #1
1283