单点时限: 3.0 sec
内存限制: 1024 MB
QQ小方以前不会算递推数列的通项公式，现在他会了，所以他急切的想教会你。
一种常见的递推数列通项公式求法是使用特征方程。
如果一个数列的递推公式为 $a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}$ ，那么他所对应的特征方程为 $r^n=c_1r_{n-1}+c_2r_{n-2}+\cdots +c_kr_{n-k}$ ，即有 $r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots -c_{k-1}r-c_k=0$ 。
如果方程 $r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots -c_{k-1}r-c_k=0$ 有 $t$ 个不同的解 $r_1,r_2,r_3\cdots r_t$ 且每个根所对应的重数为 $m_1,m_2,m_3\cdots m_t$ ，显然有 $m_i\ge 1(i\in [1,t])$ 且 $\sum_{i=1}^t m_i=k$ 。
我们可以得到数列的通项公式为 $$a_n=(\alpha {1,0}+\alpha n+\cdots +\alpha {1,m-1}n^{m_{1}-1})r_1^n\+(\alpha {2,0}+\alpha n+\cdots +\alpha {2,m-1}n^{m_{2}-1})r_2^n\+\cdots \+(\alpha {t,0}+\alpha n+\cdots +\alpha {1,m-1}n^{m_{t}-1})r_t^n$$ 。
其中 $n=1,2,3,\cdots $ ，而 $\alpha _{i,j}(1\le i\le t,0\le j\le m_i-1)$ 为一个常量，可通过前几项待定系数法求得。
单单讲给你听肯定是不够的，为了表现自己，QQ小方现在要考考你。
给定一个长度为 $n$ 的序列 ${a_n}$ ，定义 $f_1(m)=\sum_{i=1}^m a_i$ ， $f_i(m)=\sum_{j=1}^m f_{i-1}(j)(i>1)$ ，求 $f_k(n) \mod p$ 。
第一行三个整数 $n,k,p$ ( $1 \le n,k \le 10^7,1 \le p \le 100$ ，且 $p$ 为质数)。
为了减小输入规模，第二行给出三个整数 $a_1,mul,add$ ( $0 \le a_1,mul,add < p$ )，其中 $a_{i+1}=((a_i \times mul + add) \oplus i) \mod p$ ( $i\ge 1$ )。
$\oplus$ 代表按位异或运算。
一行一个整数，代表 $f_k(n) \mod p$ 。
3 3 7 0 3 4
4
5 5 13 10 3 9
4
在第一组数据中， ${a_i}=0,5,3$ ; ${f_1(i)}=0,5,1$ ; ${f_2(i)}=0,5,6$ ; ${f_3(i)}=0,5,4$ 。