Sequence Reduction

Given a positive integer n and four integers a, b, c and p, consider the sequence

1, 2, 3, \( \ldots \), n

We define an operation on any sequence \(S = [s_1, s_2, \ldots, s_k]\) which produces a new sequence \(T\) of length \(k-1\) as follows:

T_i = a \cdot s_i + b \cdot s_i+1 + c, for 1 \(\le i \le\) k-1

This operation is applied repeatedly until only one number remains. Output the final number modulo p.

For example, for n = 3 the process is:

• Initial sequence: [1, 2, 3]
• After one operation: [1\(\cdot\)a + 2\(\cdot\)b + c, 2\(\cdot\)a + 3\(\cdot\)b + c]
• Final result: (first element)\(\cdot\)a + (second element)\(\cdot\)b + c

A combinatorial analysis shows that if we denote \(L = n-1\), the final answer is given by

\[ R = (a+b)^L + b \cdot L \cdot (a+b)^{L-1} + c \cdot \frac{(a+b)^L - 1}{(a+b) - 1} \quad \text{if} \; a+b \neq 1, \]

and when \(a+b = 1\) the recurrence simplifies to

\[ R = 1 + L \cdot (b+c). \]

Output \(R \mod p\).

inputFormat

The input consists of a single line containing five integers separated by spaces: n a b c p.

n is the length of the initial sequence, and a, b, c are parameters for the operation. p is the modulus.

outputFormat

Output a single integer which is the final number obtained after repeatedly performing the operation, taken modulo p.

sample

2 1 2 3 1000

8