配点: $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$ 的长度不超过 $1,000,000$，由字符 D, I, S, C, O 组成。
• $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