#P17856. [Ontak2019]SUB

[Ontak2019]SUB

— 不同子序列计数

给定长度为 nn 的 DNA 字符串 ss,仅包含 A、C、G、T。

回答 qq 次询问。每次给出 l,rl,r,求子串 s[l..r]s[l..r] 中有多少个不同的非空子序列,答案对 109+710^9+7 取模。

子序列通过删除任意个字符、保持剩余字符顺序得到。内容相同的子序列只计算一次,即使它们来自不同的下标选择。

输入格式

第一行两个整数 n,qn,q。第二行字符串 ss。接下来 qq 行,每行两个整数 l,rl,r。

输出格式

输出 qq 行,每行一个询问的答案。

数据范围

1≤n,q≤5000001\le n,q\le500000,1≤l≤r≤n1\le l\le r\le n。

子任务 附加限制 分值
1 n,q≤15n,q\le15 10
2 n,q≤25n,q\le25
3 n≤5000n\le5000 15
4 q≤100q\le100
5 n≤50000n\le50000 25
6 无

样例 1

输入:

11 5
ACGAAATATAC
7 9
2 4
4 6
5 10
7 7

输出:

6
7
3
27
1