暂无测试数据。

掷标枪是田径运动中的一个投掷项目。运动员经过助跑后把标枪投掷出去。

春节假期，蒜头君约上他的小伙伴一块儿掷标枪。

总共有 $n$ 个人，所有人依次从同一起点开始向同一方向掷标枪，第 $i$ 个人投掷的距离为 $x_i$。

蒜头君想要让运动更加有趣，他会统计每个人投出标枪落点的前/后最近标枪的位置，若落点后最近的标枪位于 $behind$，落点前最近的标枪位于 $front$，则满足 $behind < x_i < front$。此时蒜头君给这位小伙伴记：$behind + front$ 分，如果：

• 标枪落点后方无标枪，则让 $behind = 0$；
• 标枪落点前方无标枪，则让 $front = 0$。

现在你需要帮蒜头君计算出所有小伙伴得分的总和，并对 $10^9 + 7$ 取模。

输入格式

第一行，输入一个正整数 $n$，表示共有 $n$ 个人数。

第二行，输入四个非负整数：$A, B, C, a_1$，含义如下：

由于 $n$ 较大，因此需要通过给定的种子（$A,B,C,a_1$），按照规则生成对应的 $x_i$，规则如下：

• $i\geq 2$ 时，$a_i = (A \times a_{i-1}^2 + B\times a_{i-1} + C) \% 1000000007$
• $i \geq 1$ 时，$x_i = (a_i \% n) + 1$。

输出格式

输出一个整数，表示所有人得分的总和对 $10^9 + 7$ 取模的结果。

数据范围

对于 $20\%$ 的数据：$A = 0, B = 1, C = 1, a_1 = 0$；

对于另外 $20\%$ 的数据：$1\leq n \leq 10^3$；

对于另外 $50\%$ 的数据：$1\leq n \leq 10^5$；

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

5 2 3 2 3

18

10 2 3 4 5

90