考虑化简 \(\sum_{i=1}^n \sum_{j=1}^m \min(i, j, p)\) 得到 \(nm\) 和 \(n+m\) 的系数以及常数项。
\[\sum_{i=1}^n \sum_{j=1}^m \min(i, j, p) = \frac 16 p(p-1)(2p-1) - \frac 12 p(p-1)(n + m) + pnm
\]
考虑后缀排序，求出 \(\texttt{height}\)，建出笛卡尔树。或者后缀自动机求出 parent tree。
通过边上拆点的方式找到 \(S[l : r]\) 在树上对应位置，把 LCP 转化为树上对应节点的 LCA。
式子中有 LCA，且满足可减性，考虑利用 旧词 的 trick，维护当前节点减父亲的各项系数，树剖链加链求和。
由于 HDU 的 BUG，看不到自己提交的代码，先放个完整代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <chrono>
#include <random>
#define mid ((l + r) >> 1)
#define fi first
#define se secondusing namespace std;namespace FastIO {inline char gc() {static char buf[1<<20], *p1, *p2;if (p1 == p2) p1 = buf, p2 = buf + fread(buf, 1, 1 << 20, stdin);if (p1 == p2) return EOF;return *(p1++);}char readch() { char ch; do ch = gc(); while (ch <= 32 || ch >= 127); return ch; }template <typename T> void read(T &x) {char ch; bool op = 0; x = 0;do ch = gc(), op |= ch == '-'; while (ch < '0' || ch > '9');do x = x * 10 + (ch & 15), ch = gc(); while (ch >= '0' && ch <= '9');if (op) x = -x;}template <typename T, typename... U> void read(T &x, U &...y) { read(x), read(y...); }template <typename T> void write(const T &x, const char &ed = '\n') {static int buf[50]; int tp = 0;T u = x >= 0 ? x : (putchar('-'), -x);do buf[++tp] = u % 10, u /= 10; while (u);for (; tp; --tp) putchar(buf[tp] + 48);putchar(ed);}void write(const char* str, const char &ed = '\n') { for (const char *p = str; *p; ++p) putchar(*p); putchar(ed); }template <typename T, typename... U> void write(const T &x, const U &... y) { write(x, ' '), write(y...); }
}
using namespace FastIO;
using LL = long long;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());const int MAXN = 1e5+5;
const int MAXM = 3e5+5;
int n, q;
int str[MAXN], sa[MAXN], rk[MAXN], cnt[MAXN], tmp[MAXN], ht[MAXN];
void rsort(int m) {for (int i = 1; i <= m; ++i) cnt[i] = 0;for (int i = 1; i <= n; ++i) ++cnt[rk[i]];for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];for (int i = n; i; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
}
void calcSA() {for (int i = 1; i <= n; ++i) rk[i] = str[i], tmp[n - i + 1] = i;int m = 26;rsort(m);for (int k = 1; k == 1 || m < n; k <<= 1) {int x = 0;for (int i = 1; i <= k; ++i) tmp[++x] = n - i + 1;for (int i = 1; i <= n; ++i) if (sa[i] > k) tmp[++x] = sa[i] - k;rsort(m);memcpy(tmp, rk, (n + 1) << 2);auto cmp = [&](int x, int y) { return tmp[x] != tmp[y] || tmp[x+k] != tmp[y+k]; };rk[sa[1]] = m = 1;for (int i = 2; i <= n; ++i) rk[sa[i]] = m += cmp(sa[i-1], sa[i]);}for (int i = 1, x = 0; i <= n; ++i) {x -= !!x;if (rk[i] == 1) { ht[rk[i]] = x = 0; continue; }for (int j = sa[rk[i]-1]; i+x<=n && j+x<=n && str[i+x]==str[j+x]; ++x);ht[rk[i]] = x;}
}
int arr[MAXM];
int m, rt, fa[MAXM];
vector<int> son[MAXM];
int dep[MAXM], siz[MAXM], hvy[MAXM];
int dfn[MAXM], idx[MAXM], top[MAXM], ccnt;
void dfs1(int x) {siz[x] = 1, hvy[x] = 0, dep[x] = dep[fa[x]] + 1;for (int y : son[x]) {dfs1(y);siz[x] += siz[y];if (siz[y] > siz[hvy[x]]) hvy[x] = y;}
}
void dfs2(int x) {idx[dfn[x] = ++ccnt] = x;if (!top[x]) top[x] = x;if (!hvy[x]) return;top[hvy[x]] = top[x];dfs2(hvy[x]);for (int y : son[x]) if (y != hvy[x]) dfs2(y);
}vector<pair<int, int> > qry[MAXM];void insqry(int x, int len, int qid) {while (arr[fa[top[x]]] >= len) x = fa[top[x]];int l = dfn[top[x]], r = dfn[x];while (l < r) {int mm = (l + r) >> 1;arr[idx[mm]] >= len ? r = mm : l = mm + 1;}x = idx[l];qry[x].emplace_back(len, qid);
}int qpos[MAXN];void buildfa1() {vector<int> stk;m = n * 2 - 1;for (int i = 1; i <= m; ++i) {int lst = 0;while (!stk.empty()) {int j = stk.back();if (arr[j] >= arr[i]) { lst = j; stk.pop_back(); } else { fa[i] = j; break; }}if (lst) fa[lst] = i;stk.push_back(i);}
}void buildfa2() {for (int x = 1; x <= m; ++x) {sort(qry[x].begin(), qry[x].end(), greater<pair<int, int> >());int y = x, t = fa[x];for (auto pr : qry[x]) {if (pr.first != arr[y]) {int z = ++m;arr[z] = pr.first;fa[y] = z; y = fa[y];} qpos[pr.second] = y;}fa[y] = t;}
}void buildtree() {for (int i = 0; i <= m; ++i) son[i].clear();for (int i = 1; i <= m; ++i) son[fa[i]].push_back(i); assert(son[0].size() == 1);for (int i = 1; i <= m; ++i) top[i] = 0;rt = son[0][0], ccnt = 0, dfs1(rt), dfs2(rt);
}const int mod = 1e9+7;
const int inv2 = (mod + 1) / 2;
const int inv3 = (mod + 1) / 3;
inline int fplus(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int Fplus(int &x, int y) { return x = fplus(x, y); }
inline int fminus(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int Fminus(int x, int y) { return x = fminus(x, y); }struct Tag {int c1, ca;void clear() { c1 = ca = 0; }void addt(Tag v) { Fplus(c1, v.c1), Fplus(ca, v.ca); }
};struct Coef {int k1, ka, kab;void init(int x, int y) {auto fk1 = [](LL x) { return x * (2 * x - 1) * (x - 1) % mod * inv2 % mod * inv3 % mod; };auto fk2 = [](LL x) { return x * (x - 1) % mod * inv2 % mod; };k1 = fminus(fk1(x), fk1(y)), ka = fminus(fk2(y), fk2(x)), kab = fminus(x, y);}friend Coef operator+(const Coef &x, const Coef &y) {Coef res;res.k1 = fplus(x.k1, y.k1), res.ka = fplus(x.ka, y.ka), res.kab = fplus(x.kab, y.kab);return res;}
};struct Node {int v1, vb;void clear() { v1 = vb = 0; }void addt(Tag v, Coef c) {v1 = ((LL)v.c1 * c.k1 + (LL)v.ca * c.ka + v1) % mod;vb = ((LL)v.c1 * c.ka + (LL)v.ca * c.kab + vb) % mod;}LL calc(int b) { return ((LL)vb * b + v1) % mod; }friend Node operator+(const Node &x, const Node &y) {Node res;res.v1 = fplus(x.v1, y.v1), res.vb = fplus(x.vb, y.vb);return res;}
};namespace SGT {Coef c[MAXM<<2];Node s[MAXM<<2];Tag t[MAXM<<2];inline void addtag(int x, Tag v) { s[x].addt(v, c[x]); t[x].addt(v); }inline void spread(int x) { addtag(x<<1, t[x]); addtag(x<<1|1, t[x]); t[x].clear(); } void build(int x, int l, int r) {t[x].clear(), s[x].clear();if (l == r) return c[x].init(arr[idx[l]], arr[fa[idx[l]]]);build(x<<1, l, mid), build(x<<1|1, mid+1, r);c[x] = c[x<<1] + c[x<<1|1];}void update(int x, int l, int r, int L, int R, Tag v) {if (L <= l && R >= r) return addtag(x, v);spread(x);if (L <= mid) update(x<<1, l, mid, L, R, v);if (R > mid) update(x<<1|1, mid+1, r, L, R, v);s[x] = s[x<<1] + s[x<<1|1];}Node query(int x, int l, int r, int L, int R) {if (L <= l && R >= r) return s[x];spread(x);if (R <= mid) return query(x<<1, l, mid, L, R);if (L > mid) return query(x<<1|1, mid+1, r, L, R);return query(x<<1, l, mid, L, R) + query(x<<1|1, mid+1, r, L, R); }
}void update_path(int x, Tag v) {for (; x; x = fa[top[x]]) SGT::update(1, 1, m, dfn[top[x]], dfn[x], v);
}
Node query_path(int x) {Node res; res.clear();for (; x; x = fa[top[x]]) res = SGT::query(1, 1, m, dfn[top[x]], dfn[x]) + res;return res;
}int main() {#ifndef ONLINE_JUDGEassert(freopen("hdu2d.in", "r", stdin));assert(freopen("hdu2d.out", "w", stdout));#endifint T; read(T);while (T--) {read(n, q);for (int i = 1; i <= n; ++i) str[i] = readch() - 'a' + 1;calcSA();for (int i = 1; i <= n; ++i) arr[i*2-1] = n - sa[i] + 1, arr[i*2] = ht[i+1];for (int i = 1; i <= n * 2 + q; ++i) fa[i] = 0, qry[i].clear();buildfa1(), buildtree();for (int i = 1, l, r; i <= q; ++i) read(l, r), insqry(rk[l] * 2 - 1, r - l + 1, i);buildfa2(), buildtree();SGT::build(1, 1, m);int sum = 0;for (int i = 1; i <= q; ++i) {Tag v; v.c1 = 1, v.ca = arr[qpos[i]];Fplus(sum, query_path(qpos[i]).calc(v.ca));update_path(qpos[i], v);LL s2 = (LL)v.ca * (v.ca + 1) % mod * (v.ca + inv2) % mod * inv3 % mod;LL s1 = (LL)v.ca * (v.ca + 1) % mod * inv2 % mod;sum = (sum + (s2 - s1 + mod) * inv2) % mod; write(sum);}}return 0;
}