Description

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

Input Format

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

Output Format

Output a single integer on one line: the answer.

1 1 1 1 10 7

6

Hint

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