P1349 Generalized Fibonacci Sequence

A generalized Fibonacci sequence is a sequence of the form $a_n=p\times a_{n-1}+q\times a_{n-2}$. Given the two coefficients $p$ and $q$, the first two terms $a_1$ and $a_2$, and two integers $n$ and $m$, compute the $n$-th term $a_n$ modulo $m$.

The input contains one line with six integers: $p,q,a_1,a_2,n,m$.

Output a single integer on one line: the answer.

The $10 $-th term is $55$, and $55 \bmod 7 = 6$. **Constraints** For $100\%$ of the testdata, $p,q,a_1,a_2 \in [0,2^{31}-1]$, $1\le n,m \le 2^{31}-1$. --- $\text{upd 2023.8.23}$: Added a new set of hack testdata. Translated by ChatGPT 5