Description

You are given a positive integer $n$, and the sequence $1,2,3,\ldots,n$.

For each pair of adjacent terms, take $a$ times the left term plus $b$ times the right term, then add $c$. This produces a new sequence with $n-1$ terms:

$1\times a+2\times b+c,2\times a+3\times b +c,\ldots,(n-1)\times a+n\times b+c$.

Repeat the above operation on this new sequence to obtain more sequences. In the end, the final sequence has only one term. Find the value of this term modulo $p$.

Input Format

One line with five non-negative integers $n,a,b,c,p$.

Output Format

One integer, the answer modulo $p$.

1 1 1 1 1000000007

1

4 2 3 1 1000000007

381

23 19 17 0 1000000007

323147645

233 233 233 233 1000000000

770969703

Hint

[Sample Explanation]

Sample 2:

The sequences are:

1 2 3 4
9 14 19
61 86
381

[Constraints]

• For $80\%$ of the testdata, $p$ is a prime.

• For $100\%$ of the testdata, $1\le n\le 10^{18}$, $1\le p \le 10^{14}$, $1 \le a,b\le 10^9$, and $0\le c \le 10^9$.

Translated by ChatGPT 5