CF1832E.Combinatorics Problem

Recall that the binomial coefficient $\binom{x}{y}$ is calculated as follows ($x$ and $y$ are non-negative integers):

• if $x \lt y$, then $\binom{x}{y} = 0$;
• otherwise, $\binom{x}{y} = \frac{x!}{y! \cdot (x-y)!}$.

You are given an array $a_1, a_2, \dots, a_n$ and an integer $k$. You have to calculate a new array $b_1, b_2, \dots, b_n$, where

• $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$, and so on.

Formally, $b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353$.

Note that the array is given in a modified way, and you have to output it in a modified way as well.

回忆一下，二项式系数 $\binom{x}{y}$ 的计算方式如下（其中 $x$ 和 $y$ 为非负整数）：

• 若 $x \lt 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 = \left(\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j\right) \bmod 998244353$。

注意：输入数组以一种修改后的方式给出，且你输出的数组也需采用相同的修改方式。

The only line of the input contains six integers $n$, $a_1$, $x$, $y$, $m$ and $k$ ($1 \le n \le 10^7$; $0 \le a_1, x, y \lt m$; $2 \le m \le 998244353$; $1 \le k \le 5$).

The array $[a_1, a_2, \dots, a_n]$ is generated as follows:

• $a_1$ is given in the input;
• for $2 \le i \le n$, $a_i = (a_{i-1} \cdot x + y) \bmod m$.

输入仅包含一行，其中有六个整数 $n$、$a_1$、$x$、$y$、$m$ 和 $k$（满足 $1 \le n \le 10^7$；$0 \le a_1, x, y \lt 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$。

Since outputting up to $10^7$ integers might be too slow, you have to do the following:

Let $c_i = b_i \cdot i$ (without taking modulo $998244353$ after the multiplication). Print the integer $c_1 \oplus c_2 \oplus \dots \oplus c_n$, where $\oplus$ denotes the bitwise XOR operator.

由于输出最多 $10^7$ 个整数可能过于耗时，你需要执行以下操作：

令 $c_i = b_i \cdot i$（乘法后不取模 $998244353$）。输出整数 $c_1 \oplus c_2 \oplus \dots \oplus c_n$，其中 $\oplus$ 表示按位异或运算符。