시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 2 2 66.667%

문제

A subsequence of string $S$ is a string that can be obtained from $S$ by removing zero or more characters without changing the order of the remaining characters. For example, the string "ababA" has 24 different subsequences: (empty string), "a", "b", "A", "ab", "aa", "aA", "ba", "bb", "bA", "aba", "abb", "abA", "aab", "aaA", "bab", "baA", "bbA", "abab", "abaA", "abbA" "aabA", "babA", and "ababA". Note that we distinguish uppercase and lowercase letters in this problem.

You are given a string of length $n$, $S=c_1 c_2 \ldots c_n$, and $Q$ contiguous substrings of $S$. Calculate the number of different subsequences for each of these $Q$ substrings.

To reduce and encode input, we will use the following pseudo-random generator. The numbers $a_0$, $b_0$, $p$, $q$, and $r$ are given initially. The values $a_i$, $b_i$, $x_i$, $y_i$, $z_i$ are then produced as follows (let $z_0 = 0$ and $X = 10^9 + 7$ for convenience):

$$\begin{align*} a_i &= (p \cdot a_{i-1} + q \cdot b_{i-1} + z_{i-1} + r) \bmod X \\ b_i &= (p \cdot b_{i-1} + q \cdot a_{i-1} + z_{i-1} + r) \bmod X \\ x_i &= \min(a_i \bmod n, b_i \bmod n) + 1 \\ y_i &= \max(a_i \bmod n, b_i \bmod n) + 1 \\ z_i &= \big(\text{the number of different subsequences of } c_{x_i} c_{x_i+1} \ldots c_{y_i-1} c_{y_i}\big) \end{align*} $$

Your program must print only one integer: the value $z_Q$.

입력

The first line contains the string $S$ which can contain uppercase and lowercase English letters. The length of $S$ is between $1$ and $10^6$ letters, inclusive.

The second line contains six integers $Q$, $a_0$, $b_0$, $p$, $q$, and $r$ ($1 \leq Q \leq 10^6$, $0 \leq a_0, b_0, p, q, r < X = 10^9 + 7$).

출력

Print the integer $z_Q$.

예제 입력 1

ababA
2 4 6 8 10 12

예제 출력 1

7