题目背景

题目描述

小 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}$。

输出格式

共一行一个非负整数，为题目中所求的答案。

2 0 1 1 1

11

9 0 1 0 663

422994

20 1 0 0 998244353

560706529

114514 17723 134 1045 233337

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$		AB
$2$	$1000$	无
$3$
$4$	$5000$
$5$
$6$	$10^4$	A
$7$	$10^5$
$8$		B
$9$		无
$10$	$2\times 10^5$	A
$11$		B
$12$	$5\times 10^5$	无
$13$	$10^6$	A
$14$		B
$15$	$2\times 10^6$	无
$16$	$3\times 10^6$
$17$	$5\times 10^6$	A
$18$	$10^7$
$19$		B
$20$	$1.3\times 10^7$	无
$21$	$1.6\times 10^7$
$22$	$2\times 10^7$	A
$23$		B
$24$		无
$25$

特殊性质 A：保证所有 $g_i$ 相等。

特殊性质 B：保证只有 $g_n\neq 0$。