字符串 $S$ 的子序列是指通过删除 $S$ 中的零个或多个字符，且不改变剩余字符顺序而得到的字符串。例如，字符串 “ababA” 有 24 个不同的子序列：（空字符串）、“a”、“b”、“A”、“ab”、“aa”、“aA”、“ba”、“bb”、“bA”、“aba”、“abb”、“abA”、“aab”、“aaA”、“bab”、“baA”、“bbA”、“abab”、“abaA”、“abbA”、“aabA”、“babA” 和 “ababA”。注意，在本题中，我们区分大小写字母。

给定一个长度为 $n$ 的字符串 $S = c_1c_2 \dots c_n$，以及 $S$ 的 $Q$ 个连续子串。请计算这些 $Q$ 个子串中每一个所包含的不同子序列的数量。

为了简化和编码输入，我们将使用以下伪随机生成器。初始给定数字 $a_0, b_0, p, q$ 和 $r$。随后按如下方式生成 $a_i, b_i, x_i, y_i, z_i$（令 $z_0 = 0$ 且 $X = 10^9 + 7$）：

$$a_i = (p \cdot a_{i-1} + q \cdot b_{i-1} + z_{i-1} + r) \pmod X$$ $$b_i = (p \cdot b_{i-1} + q \cdot a_{i-1} + z_{i-1} + r) \pmod X$$ $$x_i = \min(a_i \pmod n, b_i \pmod n) + 1$$ $$y_i = \max(a_i \pmod n, b_i \pmod n) + 1$$ $$z_i = (\text{字符串 } c_{x_i}c_{x_i+1} \dots c_{y_i-1}c_{y_i} \text{ 的不同子序列数量})$$

你的程序只需输出一个整数：$z_Q$ 的值。

输入格式

第一行包含字符串 $S$，其中可以包含大小写英文字母。$S$ 的长度在 $1$ 到 $10^6$ 之间（含边界）。

第二行包含六个整数 $Q, a_0, b_0, p, q$ 和 $r$ ($1 \le Q \le 10^6, 0 \le a_0, b_0, p, q, r < X = 10^9 + 7$)。

输出格式

输出整数 $z_Q$。

样例

样例输入 1

ababA
2 4 6 8 10 12

样例输出 1

7