P2461 [SDOI2008] Recursive Sequence

A sequence of natural numbers is defined as follows: For $i \le k$: $a_{i}= b_{i}$. For $i > k$: $a_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}$. Here $b_{1\dots k}$ and $c_{1\dots k}$ are given natural numbers. Write a program that, given natural numbers $m \le n$, computes $\left( \sum_{i=m}^{n}{a_{i}} \right) \bmod p$.

The first line contains a natural number $k$. The second line contains $k$ natural numbers $b_{1}, b_{2}, \dots, b_{k}$. The third line contains $k$ natural numbers $c_{1}, c_{2}, \dots, c_{k}$. The fourth line contains three natural numbers $m, n, p$.

Output one positive integer on a single line, representing the value of $\sum_{i=m}^{n}{a_{i}} \mod p$.

For $20\%$ of the testdata, $n \le 10^{6}$. For another $30\%$ of the testdata, $k=1$. For $100\%$ of the testdata, $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}$. Translated by ChatGPT 5