P2461 [SDOI2008] 递归数列

一个由自然数组成的数列按下式定义： 对于 $i \le k$：$a_{i}= b_{i}$。 对于 $i > k$：$a_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}$。 其中 $b_{1\dots k}$ 和 $c_{1\dots k}$ 是给定的自然数。 写一个程序，给定自然数 $m \le n$，计算 $\left( \sum_{i=m}^{n}{a_{i}} \right) \bmod p$。

无

无

对于 $20\%$ 的数据，$n \le 10^{6}$。 对于另外 $30\%$ 的数据，$k=1$。 对于 $100\%$ 的数据，$1 \le k \le 15$，$1 \le m \le n \le 10^{18}$，$0 \le b_{i},c_{i} \le 10^{9}$，$p \le 10^{8}$。