574. 通项公式

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