Problem Description

Takahashi wrote a string $ S $. Answer the following $ Q $ queries.

• Query $ q $ $(1\ \leq\ q\ \leq\ Q)$: Given integers $L_q,\ R_q$. How many tuples $(i,\ j,\ k,\ l,\ m)$ $(L_q\ \leq\ i\ <\ j\ <\ k\ <\ l\ <\ m\ \leq\ R_q)$ exist such that $ S_i $ = D, $ S_j $ = I, $ S_k $ = S, $ S_l $ = C, $ S_m $ = O? Find the count modulo $ 2^{32} $.

Input Format

The input is given from the standard input in the following format:

$ S $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ L_3 $ $ R_3 $ $ : $ $ L_Q $ $ R_Q $

Output Format

Output $ Q $ lines. The $ q $-th line should contain the answer to query $ q $.

Sample Input and Output

Sample Input #1

DDDDDDISCOOOOOO
7
6 10
5 11
4 12
3 13
2 14
1 15
1 8

Sample Output #1

1
4
9
16
25
36
0

Sample Input #2

DDDIIISSSCCCOOO
12
1 12
1 13
1 14
1 15
2 12
2 13
2 14
2 15
3 13
3 14
3 15
4 15

Sample Output #2

0
81
162
243
0
54
108
162
27
54
81
0

Notes/Hints

Constraints

• $ S $ is a string of length at most $1\ 000\ 000$ consisting of D, I, S, C, O.
• $1\ \leq\ Q\ \leq\ 100\ 000$
• $1\ \leq\ L_q\ \leq\ R_q\ \leq\ |S|$
• $L_q,\ R_q$ are integers

见题面 Input 部分

见题面 Output 部分