组合数卷积

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

规定 $x<y$ 时 $\binom{x}{y}=0$。给定数组 $a_1,\ldots,a_n$ 与整数 $k$，定义

$$b_i=\left(\sum_{j=1}^{i}\binom{i-j+1}{k}a_j\right)\bmod 998244353.$$

数组 $a$ 由输入参数递推生成。令 $c_i=b_i\cdot i$，注意该乘法之后不再取模。求

$$c_1\oplus c_2\oplus\cdots\oplus c_n,$$

其中 $\oplus$ 表示按位异或。

输入格式

输入一行六个整数 $n,a_1,x,y,m,k$。对 $2\le i\le n$，有

$$a_i=(a_{i-1}x+y)\bmod m.$$

输出格式

输出一个整数，表示所有 $b_i\cdot i$ 的按位异或和。

样例输入 1

5 8 2 3 100 2

样例输出 1

1283

数据范围

对于所有数据：$1\le n\le10^7$，$0\le a_1,x,y<m$，$2\le m\le998244353$，$1\le k\le5$。

子任务编号	分值	特殊限制
1	20	$n\le2000$ 且 $k\ge2$
2	40	$k=1$
3		无特殊限制