A15877 | Combinatorics Problem

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

- if $x < 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.

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 < 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$ .

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.