该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Journey - Kirara Magic / ugumugu

题目描述

小 W 最近正在学习某编程语言。

这个编程语言有个语句如下：

range(a,b,c)

这个语句表示一个序列，这个序列是这样的：

其中，$k$ 是最大的满足 $a+kc<b$ 的非负整数 $k$。例如 range(1,7,2) 表示的序列为 $[1,3,5]$。

小 W 想问你一个问题：给你一个长为 $n$ 的序列 $g$（下标从 $1$ 开始），求出下列式子的值，答案模 $10^9 +7$。

输入格式

为了加快读入速度，我们采用以下读入方法。

读入共一行五个非负整数 $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

样例 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$。

9 0 1 0 663

422994

样例 2 解释

该样例满足特殊性质 A。

20 1 0 0 998244353

560706529

114514 17723 134 1045 233337

442762986

数据范围

对于 $100\%$ 的数据：$1\leq n\leq 2\times 10^7$，$0\leq A,B,C,g_n<10^9 +7$。

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

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