반복 부분열 테스트

어떤 문자열의 부분열(subsequence)은 문자열에서 몇몇 문자를 지웠을 때 얻어지는 문자열이다. 아무 문자도 지우지 않아도 되고, 모두 지워도 된다. 예를 들어 "ababA"의 서로 다른 부분열은 ""(빈 문자열), "a", "b", "A", "ab", "aa", "aA", "ba", "bb", "bA", "aba", "abb", "abA", "aab", "aaA", "bab", "baA", "bbA", "abab", "abaA", "abbA", "aabA", "babA", "ababA"로 총 $24$개이다. 이 문제에서는 대소문자를 구별한다.

길이가 $N$인 문자열 $S$가 주어진다. 이 문자열의 연속한 부분문자열 $Q$개에 대해 각각 서로 다른 부분열의 개수를 구하는 프로그램을 작성하라.

입력을 받는 시간을 줄이기 위해 다음과 같은 의사 난수 생성기(PseudoRandom Generator)를 사용한다. $a_0$, $b_0$, $p$, $q$, $r$이 주어지면 $i \geq 1$일 때 $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) \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{의 서로 다른 부분열의 개수}) \bmod X$

$u \bmod v$는 $u$를 $v$로 나눈 나머지를 의미한다. 난수를 생성하는 방식 자체에는 의미가 없으며, 어떤 입력이 주어져도 제한 시간 안에 정답을 출력하는 알고리즘이 존재한다.

$z_Q$를 구해보자.

첫 번째 줄에 문자열 $S$가 주어진다. 이 문자열의 길이 $N$은 $1$ 이상 $10^6$ 이하이며, $S$는 알파벳 대문자와 소문자로만 이루어져 있다.

두 번째 줄에는 6개의 정수 $Q$, $a_0$, $b_0$, $p$, $q$, $r$이 공백 하나로 구분되어 주어진다. $1 \leq Q \leq 10^6$을 만족하며, $0 \leq a_0, b_0, p, q, r < X = 10^9 + 7$을 만족한다.

첫째 줄에 $z_Q$를 출력한다.