P6435 "EZEC-1" Sequence.

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

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

One integer, the answer modulo $p$.

[Sample Explanation] Sample 2: The sequences are: ``` 1 2 3 4 9 14 19 61 86 381 ``` ------------ [Constraints] | Test Point ID | $n\le$ | $p\le$ | $a,b\le$ | $c\le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1\sim 4$ | $10^3$ | $10^9+7$ | $10$ | $10$ | | $5\sim 8$ | $10^6$ | $10^{14}$ | $10^3$ | $10^3$ | | $9,10$ | $10^9$ | $10^9+7$ | $1$ | $0$ | | $11,12$ | $10^9$ | $10^9+7$ | $1$ | $10^9$ | | $13,14$ | $10^{18}$ | $10^9+7$ | $1$ | $10^9$ | | $15,16$ | $10^{18}$ | $10^9+7$ | $10^9$ | $10^9$ | | $17 \sim 20$ | $10^{18}$ | $10^{14}$ | $10^9$ | $10^9$ | - 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