暂无测试数据。

要创造新的世界，必须吸取大地的精魂作为材料。要吸取大地的精魂就必须在大地上开出洞穴来，大地可以看成一个数轴，约翰会不断地在大地上的某一个整数点开一个洞穴，这个洞穴能分别从他左右两边第一个已经开出的洞穴吸取大地之魂，数量等于对应洞穴的坐标。如果某一个方向没有洞穴，那么这个洞穴就无法从这个方向吸收大地之魂。约翰可以在一个坐标上开多个洞穴，每次吸收的大地之魂的数量都会累加。

现在给出约翰的操作序列，约翰想知道他一共能吸收多少大地之魂。你只需要告诉他模 $10^9+7$ 之后的数量就可以了。

输入格式

一行 $5$ 个整数 $n,A,B,C,x_1$。

$n$ 代表操作序列的长度，$A,B,C$和 $x_1$ 的含义见下。

操作序列按如下方式生成：给定 $x_1$ 和参数 $A,B,C$，对于 $2 \le i \le n$，$x_i=(A*x^2_{i-1}+B*x_{i-1}+C) \mod (10^9+7)$。

设操作序列为 $a$，对于 $1 \le i \le n$，$a_i=(x_i\%n)+1$。

$a_i$ 代表第 $i$ 个打开的洞穴的坐标。

输出格式

一行一个整数，代表吸取的大地之魂的总数模 $10^9+7$ 的值。

数据规模

对于 $10\%$ 的数据：$A=0,B=1,C=1,x_1=0$。

对于另外 $20\%$ 的数据：$n \le 1000$。

对于另外 $30\%$ 的数据：$n \le 100000$。

对于 $100\%$ 的数据，$n \le 6000000$，$0 \le A,B,C,x_1 < 10^9 + 7$。

样例解释

样例 1：操作序列为 4 5 2 3 5。

样例 2：操作顺序为 6 10 4 2 10 6 6 9 9 4。

5 2 3 2 3

18

10 2 3 4 5

90