Generalized Fibonacci Sequence Modulo

Consider a generalized Fibonacci sequence defined by the recurrence relation \(a_n = p \times a_{n-1} + q \times a_{n-2}\). You are given the coefficients \(p\) and \(q\), and the first two terms \(a_1\) and \(a_2\) of the sequence. In addition, two integers \(n\) and \(m\) are provided. Your task is to compute the \(n\)th term \(a_n\) of the sequence modulo \(m\).

Input: Six integers \(p, q, a_1, a_2, n, m\) on a single line separated by spaces.

Output: A single integer representing \(a_n \bmod m\).

Note: All formulas are presented in \(\LaTeX\) format.

inputFormat

The input consists of a single line containing six space-separated integers:

1. \(p\): The coefficient for \(a_{n-1}\).
2. \(q\): The coefficient for \(a_{n-2}\).
3. \(a_1\): The first term of the sequence.
4. \(a_2\): The second term of the sequence.
5. \(n\): The index of the term to compute.
6. \(m\): The modulus value.

outputFormat

Output a single integer, the value of \(a_n \bmod m\).

sample

1 1 1 1 5 100

5