574. 通项公式

QQ小方以前不会算递推数列的通项公式，现在他会了，所以他急切的想教会你。

一种常见的递推数列通项公式求法是使用特征方程。

如果一个数列的递推公式为 $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$ ，那么他所对应的特征方程为 $r^n=c_1{r}_{n-1}+c_2{r}_{n-2}+\cdots +c_k{r}_{n-k}$ ，即有 $r^k-c_1{r}^{k-1}-c_2{r}^{k-2}-\cdots -c_{k-1}r-c_k=0$ 。

如果方程 $r^k-c_1{r}^{k-1}-c_2{r}^{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)\mathrm{mod}p$ 。