子串的故事（2）

Problem Description

对于一个包含字符串 $s_1, s_2, \cdots, s_k$ 的字符串可重集 $T$，定义 $T$ 的价值为

$$\sum\limits_{1 \leq i < j \leq k} \mathrm{LCP}(s_i, s_j) $$

给出一个长度为 $n$ 的字符串 $S$，下标从 $1$ 到 $n$。有一个初始为空的字符串集合 $T$。 有 $m$ 次操作，每次操作给出两个正整数 $l, r(1 \leq l \leq r \leq n)$，你需要将字符串 $S[l : r]$ 的所有前缀都加入集合 $T$。形式化地，对于所有 $l \leq i \leq r$，你需要将 $S[l : i]$ 加入集合 $T$。 每次操作过后，你都需要求出此刻集合 $T$ 的价值。答案对 $10^9 + 7$ 取模。 $\dagger$ $\mathrm{LCP}(s_i, s_j)$：字符串 $s_i, s_j$ 的最长公共前缀的长度。 $\dagger$ $S[l : r]$：字符串 $S$ 从第 $l$ 到第 $r$ 位的字符组成的子串，即 $S_lS_{l+1}\cdots S_r$。

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T(1 \leq T \leq 5 \times 10^5)$，表示数据组数。对于每组测试数据： 第一行两个正整数 $n, m(1 \leq n, m \leq 10^5)$，分别表示字符串长度和操作次数。 第二行一个长度为 $n$ 的字符串 $S$，字符串 $S$ 只包含小写拉丁字母（从 a 到 z，共 $26$ 个）。 接下来 $m$ 行，每行两个正整数 $l, r(1 \leq l \leq r \leq n)$，表示将字符串 $S[l : r]$ 的所有前缀都加入集合 $T$。 保证所有测试数据中 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

Output

对于每组测试数据：输出 $m$ 行，每行一个整数，表示每次操作过后集合 $T$ 的价值。答案对 $10^9 + 7$ 取模。

Sample Input

1
4 5
aaba
1 2
1 4
2 3
3 4
3 3

Sample Output

1
22
35
36
38

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（2）