配点: $700$ 点

問題文

高橋君は文字列 $S$ を書きました。次の $Q$ 個の質問に答えてください。

• 質問 $q$ $(1 \\leq q \\leq Q)$: 整数 $L_q, R_q$ が与えられる。$S_i$ = D, $S_j$ = I, $S_k$ = S, $S_l$ = C, $S_m$ = O であるような組 $(i, j, k, l, m)$ $(L_q \\leq i < j < k < l < m \\leq R_q)$ は何個存在するか？その個数を $2^{32}$ で割った余り を求めよ。

制約

• $S$ は D, I, S, C, O から構成される長さ $1 \\ 000 \\ 000$ 以下の文字列
• $1 \\leq Q \\leq 100 \\ 000$
• $1 \\leq L_q \\leq R_q \\leq |S|$
• $L_q, R_q$ は整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$Q$ 行出力せよ。$q$ 行目に質問 $q$ に対する答えを出力すること。

入力例 1

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

出力例 1

1
4
9
16
25
36
0

入力例 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

出力例 2

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