#P17856. [Ontak2019]SUB
[Ontak2019]SUB
— 不同子序列计数
给定长度为 的 DNA 字符串 ,仅包含 A、C、G、T。
回答 次询问。每次给出 ,求子串 中有多少个不同的非空子序列,答案对 取模。
子序列通过删除任意个字符、保持剩余字符顺序得到。内容相同的子序列只计算一次,即使它们来自不同的下标选择。
输入格式
第一行两个整数 。第二行字符串 。接下来 行,每行两个整数 。
输出格式
输出 行,每行一个询问的答案。
数据范围
,。
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2 | ||
| 3 | 15 | |
| 4 | ||
| 5 | 25 | |
| 6 | 无 |
样例 1
输入:
11 5
ACGAAATATAC
7 9
2 4
4 6
5 10
7 7
输出:
6
7
3
27
1