Problem Description

Little W is currently learning a certain programming language.

This programming language has a statement as follows:

range(a,b,c)

This statement represents a sequence, which is defined as:

$$ [a, a+c, a+2c, \cdots, a+kc] $$

where $k$ is the largest non-negative integer such that $a+kc < b$. For example, range(1,7,2) represents the sequence $[1,3,5]$.

Little W wants to ask you a question: Given a sequence $g$ of length $n$ (indexed from 1), compute the value of the following expression, modulo $10^9 + 7$.

$$ \sum_{a=1}^{n}\sum_{b=a+1}^{n+1}\sum_{c=1}^{n}\sum_{i \in \mathrm{range}(a,b,c)} g_i $$

Input Format

To speed up the input, we use the following method.

The input consists of one line with five non-negative integers $n, A, B, C, g_n$.

Here, $n$ is the length of the sequence $g$, and $A, B, C$ are parameters for generating the data, with $g_n$ being the $n$-th element of the sequence $g$.

For the $i$-th element of the sequence $g$ (where $1 \leq i < n$), it satisfies $g_i \equiv A g_{i+1}^2 + B g_{i+1} + C \pmod{10^9 + 7}$.

Output Format

Output a single non-negative integer, which is the answer to the problem.

Sample Input and Output

Sample Input #1

2 0 1 1 1

Sample Output #1

11

Sample Input #2

9 0 1 0 663

Sample Output #2

422994

Sample Input #3

20 1 0 0 998244353

Sample Output #3

560706529

Sample Input #4

114514 17723 134 1045 233337

Sample Output #4

442762986

Notes

Sample Explanation #1

$g = [2, 1]$ (indexed from 1)

Let $= \sum_{i \in \mathrm{range}(a,b,c)} g_i$.

When $a=1, b=2, c=1$, $ans = 2$.

When $a=1, b=2, c=2$, $ans = 2$.

When $a=1, b=3, c=1$, $ans = 2 + 1 = 3$.

When $a=1, b=3, c=2$, $ans = 2$.

When $a=2, b=3, c=1$, $ans = 1$.

When $a=2, b=3, c=2$, $ans = 1$.

The answer is $\sum ans = 2 + 2 + 3 + 2 + 1 + 1 = 11$.

Sample Explanation #2

This sample satisfies special property A.

Data Range

For $100\%$ of the data: $1 \leq n \leq 2 \times 10^7$, $0 \leq A, B, C, g_n < 10^9 + 7$.

Special Property A: All $g_i$ are equal.

Special Property B: Only $g_n \neq 0$.

见题面 Input 部分

见题面 Output 部分