D - DISCO! Editorial /

Time Limit: 13 sec / Memory Limit: 1024 MB

配点: 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