【MX-S3-T2】「FeOI Round 1」Journey
题目背景
题目描述
小 W 最近正在学习某编程语言。
这个编程语言有个语句如下：
```
range(a,b,c)
```
这个语句表示一个序列，这个序列是这样的：
$$
[a,a+c,a+2c,\cdots,a+kc]
$$
其中，$k$ 是最大的满足 $a+kc<b$ 的非负整数 $k$。例如 `range(1,7,2)` 表示的序列为 $[1,3,5]$。
小 W 想问你一个问题：给你一个长为 $n$ 的序列 $g$（下标从 $1$ 开始），求出下列式子的值，答案模 $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
$$
输入输出格式
输入格式
为了加快读入速度，我们采用以下读入方法。
读入共一行五个非负整数 $n,A,B,C,g_n$。
其中 $n$ 为序列 $g$ 的长度，$A,B,C$ 为生成数据的参数，$g_n$ 为序列 $g$ 的第 $n$ 项。
对于序列 $g$ 的第 $i$（$1\leq i < n$）项，满足 $g_i \equiv Ag_{i+1}^2+Bg_{i+1}+C \pmod {10^9 + 7}$。
输出格式
共一行一个非负整数，为题目中所求的答案。
输入输出样例
输入样例 #1
2 0 1 1 1输出样例 #1
11输入样例 #2
9 0 1 0 663输出样例 #2
422994输入样例 #3
20 1 0 0 998244353输出样例 #3
560706529输入样例 #4
114514 17723 134 1045 233337输出样例 #4
442762986说明
**【样例解释 #1】**
$g=[2,1]$（下标从 $1$ 开始）
令 $ans=\sum\limits_{i\in \mathrm{range}(a,b,c)} g_i$。
当 $a=1,b=2,c=1$ 时，$ans=2$。
当 $a=1,b=2,c=2$ 时，$ans=2$。
当 $a=1,b=3,c=1$ 时，$ans=2+1=3$。
当 $a=1,b=3,c=2$ 时，$ans=2$。
当 $a=2,b=3,c=1$ 时，$ans=1$。
当 $a=2,b=3,c=2$ 时，$ans=1$。
答案为 $\sum ans=2+2+3+2+1+1=11$。
**【样例解释 #2】**
该样例满足特殊性质 A。
**【数据范围】**
对于 $100\%$ 的数据：$1\leq n\leq 2\times 10^7$，$0\leq A,B,C,g_n<10^9 +7$。
| 测试点编号 | $n=$ | 特殊性质 |
| :--------: | :--------------: | :------: |
| $1$ | $1$ | AB |
| $2$ | $1000$ | 无 |
| $3$ | $1000$ | 无 |
| $4$ | $5000$ | 无 |
| $5$ | $5000$ | 无 |
| $6$ | $10^4$ | A |
| $7$ | $10^5$ | A |
| $8$ | $10^5$ | B |
| $9$ | $10^5$ | 无 |
| $10$ | $2\times 10^5$ | A |
| $11$ | $2\times 10^5$ | B |
| $12$ | $5\times 10^5$ | 无 |
| $13$ | $10^6$ | A |
| $14$ | $10^6$ | B |
| $15$ | $2\times 10^6$ | 无 |
| $16$ | $3\times 10^6$ | 无 |
| $17$ | $5\times 10^6$ | A |
| $18$ | $10^7$ | A |
| $19$ | $10^7$ | B |
| $20$ | $1.3\times 10^7$ | 无 |
| $21$ | $1.6\times 10^7$ | 无 |
| $22$ | $2\times 10^7$ | A |
| $23$ | $2\times 10^7$ | B |
| $24$ | $2\times 10^7$ | 无 |
| $25$ | $2\times 10^7$ | 无 |
特殊性质 A：保证所有 $g_i$ 相等。
特殊性质 B：保证只有 $g_n\neq 0$。