Repeating Subsequence Tests

A subsequence of a string is the string that remains after removing some of its characters. You may remove no characters, or all of them. For example, the distinct subsequences of "ababA" are "" (the 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", 24 in total. This problem treats uppercase and lowercase letters as different.

You are given a string $S$ of length $N$. Write a program that finds, for each of $Q$ contiguous substrings of $S$, the number of distinct subsequences of that substring.

To reduce input time, the problem uses the following pseudorandom generator. Given $a_0$, $b_0$, $p$, $q$, $r$, for $i \geq 1$ the values $a_i$, $b_i$, $x_i$, $y_i$, and $z_i$ are defined as follows. First, let $z_0 = 0$ and $X = 10^9 + 7$.

$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 = (c_{x_i} c_{x_i+1} \ldots c_{y_i-1} c_{y_i}\text{ has this many distinct subsequences}) \bmod X$

$u \bmod v$ is the remainder when $u$ is divided by $v$. The way the generator produces its numbers has no meaning, and for any input there is an algorithm that outputs the answer within the time limit.

Find $z_Q$.

The first line contains the string $S$. Its length $N$ satisfies $1$ to $10^6$, and $S$ consists only of uppercase and lowercase English letters.

The second line contains six integers $Q$, $a_0$, $b_0$, $p$, $q$, $r$, separated by single spaces. It is given that $1 \leq Q \leq 10^6$ and $0 \leq a_0, b_0, p, q, r < X = 10^9 + 7$.

On the first line, print $z_Q$.