题目描述
Problem Description
Given a positive integer \( n \), consider the sequence \( 1, 2, 3, \ldots, n \).
Calculate the sum of the product of the left term and \( a \) plus the product of the right term and \( b \) plus \( c \) for each pair of adjacent terms, resulting in 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 several sequences, until the final sequence has only one term. Find the value of this final term modulo \( p \).
Input Format
One line containing five non-negative integers \( n, a, b, c, p \).
Output Format
An integer representing the answer modulo \( p \).
Sample Input and Output
Sample Input #1
1 1 1 1 1000000007
Sample Output #1
1
Sample Input #2
4 2 3 1 1000000007
Sample Output #2
381
Sample Input #3
23 19 17 0 1000000007
Sample Output #3
323147645
Sample Input #4
233 233 233 233 1000000000
Sample Output #4
770969703
Notes
Sample Explanation
Sample 2:
The sequences are:
1 2 3 4
9 14 19
61 86
381
Data Range
| Test Case Number | \( 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 data, \( p \) is a prime number.
-
For \( 100\% \) of the data, \( 1 \le n \le 10^{18} \), \( 1 \le p \le 10^{14} \), \( 1 \le a, b \le 10^9 \), \( 0 \le c \le 10^9 \).
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分