#P18173. Bracket Sequence
Bracket Sequence
Bracket Sequence
称一个括号序列是好的,当且仅当它由若干个 () 依次拼接而成。形式化地,长度为 的序列满足:奇数位置均为 (,偶数位置均为 )。称这样的序列深度为 。
例如 ()、()()、()()() 都是好的;(()) 不是好的。这里的“深度”指 () 的个数,并不是通常括号序列的嵌套深度。
给定长度为 的括号字符串 ,下标从 1 开始。定义 为子串 中,深度为 的好子序列数量。
子序列可以不连续,但必须保留原顺序;选择的下标集合不同就视为不同子序列,即使得到的括号字符串相同。
需要回答 个询问,每个询问给出 :
- 若 ,输出 ;
- 若 ,输出
所有答案对 取模。字符串不会修改。
输入格式
第一行两个整数 ,满足 、。
第二行一个长度为 的字符串 ,仅由 ( 和 ) 组成。
接下来 行,每行四个整数 ,满足
$$op\in\{1,2\},\qquad1\le l\le r\le n,\qquad1\le k\le20.$$输出格式
对每个询问输出一行一个整数,表示对应答案模 的结果。
样例
输入:
5 20
(()()
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 2 3 1
1 2 4 1
1 2 5 1
1 3 4 1
1 3 5 1
1 4 5 1
2 1 3 1
2 1 4 1
2 1 5 1
2 2 3 1
2 2 4 1
2 2 5 1
2 3 5 1
2 4 5 1
1 1 5 2
2 1 5 2
输出:
0
2
2
5
1
1
3
0
1
1
3
6
16
1
2
7
2
1
2
3