Background

Original link: https://oier.team/problems/S3B。

---

Problem Description

Little W has recently been learning a programming language.

This programming language has a statement as follows:

range(a,b,c)

This statement represents a sequence, and the sequence is:

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

Here, $k$ is the largest non-negative integer $k$ 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 starting from $1$), compute the value of the following expression, and output the answer modulo $10^9 +7$.

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

Input Format

To speed up input, we use the following input 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$, $A, B, C$ are parameters for generating the data, and $g_n$ is the $n$-th term of the sequence $g$.

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

Output Format

Output one line with one non-negative integer, which is the required answer in the problem.

2 0 1 1 1

11

9 0 1 0 663

422994

20 1 0 0 998244353

560706529

114514 17723 134 1045 233337

442762986

Hint

Sample Explanation #1

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

Let $ans=\sum\limits_{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.

Constraints

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

Test Point ID	$n=$	Special Property
$1$		AB
$2$	$1000$	None
$3$
$4$	$5000$
$5$
$6$	$10^4$	A
$7$	$10^5$
$8$		B
$9$		None
$10$	$2\times 10^5$	A
$11$		B
$12$	$5\times 10^5$	None
$13$	$10^6$	A
$14$		B
$15$	$2\times 10^6$	None
$16$	$3\times 10^6$
$17$	$5\times 10^6$	A
$18$	$10^7$
$19$		B
$20$	$1.3\times 10^7$	None
$21$	$1.6\times 10^7$
$22$	$2\times 10^7$	A
$23$		B
$24$		None
$25$

Special Property A: it is guaranteed that all $g_i$ are equal.

Special Property B: it is guaranteed that only $g_n\neq 0$.

Translated by ChatGPT 5