Description

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

Input Format

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 Format

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

2
1 1
1 1
2 10 1000003

142

Hint

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