Description：

多次询问区间本质不同回文子串数。

$1\leqslant n\leqslant 300000$

Solution：

考虑扫描线，把所有询问按右端点排序，然后每到一个点就把以这个点为后缀的所有回文子串加进去，那么有一个结论是以一个点为结尾的所有回文串会形成不超过 $\log$ 个等差数列，考虑一个等差数列对于答案的贡献，会发现其实是从最长的那个串上一次出现的位置的左端点 $+1$ 到最小的串的左端点这些位置答案加一，那么我们可以用线段树维护回文树上每个回文串最后一次出现的位置，然后把等差的部分跳过，具体做法是把 $fail$ 树建出来，然后用线段树维护 $dfs$ 序，那么这个点最后一次出现就是子树中所有串最后一次出现的时间的最大值，最后用树状数组区间加单点求值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

#define MAXN 300010

#define MAXM 1000010

int n,m;

char c[MAXN];

namespace PAM

{

	struct node

	{

		int tr[26],fail,len;

	}t[MAXN];

	int ptr = 0,last = 0;

	int newnode(int l)

	{

		int k = ptr;

		memset(&t[k],0,sizeof(&t[k]));

		t[k].len = l;

		return ptr++;

	}

	void init()

	{

		ptr = last = 0;

		newnode(0);newnode(-1);

		t[0].fail = t[1].fail = 1;

		return;

	}

	int getfail(int i,int p)

	{

		while(c[i - t[p].len - 1] != c[i])p = t[p].fail;

		return p;

	}

	int nxt[MAXN],diff[MAXN];

	int pos[MAXN];

	int extend(int i,int k)

	{

		int p = getfail(i,last);

		if(t[p].tr[k] == 0)

		{

			int np = newnode(t[p].len + 2);

			t[np].fail = t[getfail(i,t[p].fail)].tr[k];

			t[p].tr[k] = np;

			diff[np] = t[np].len - t[t[np].fail].len;

			if(diff[np] == diff[t[np].fail])nxt[np] = nxt[t[np].fail];

			else nxt[np] = np;

		}

		last = t[p].tr[k];

		return last;

	}

	struct edge

	{

		int to,nxt;

	}e[MAXN];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b)

	{

		if(a == b)return;

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		return;

	}

	void build()

	{

		for(int i = 0;i < ptr;++i)add(t[i].fail,i);

		return;

	}

	int ind[MAXN],oud[MAXN],tot = 0;

	void dfs(int k)

	{

		ind[k] = ++tot;

		for(int i = lin[k];i != 0;i = e[i].nxt)dfs(e[i].to);

		oud[k] = tot;

		return;

	}

}

namespace ST

{

	struct node

	{

		int lc,rc;

		int maxv;

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void change(int rt,int p,int v,int l,int r)

	{

		if(l == r){t[rt].maxv = v;return;}

		if(p <= mid)change(t[rt].lc,p,v,l,mid);

		else change(t[rt].rc,p,v,mid + 1,r);

		t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

		return;

	}

	int query(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)return t[rt].maxv;

		if(R <= mid)return query(t[rt].lc,L,R,l,mid);

		if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

		return max(query(t[rt].lc,L,R,l,mid),query(t[rt].rc,L,R,mid + 1,r));

	}

}

namespace BIT

{

	int v[MAXN];

	int lowbit(int x){return x & (-x);}

	void add(int p,int x){for(int i = p;i <= n;i += lowbit(i))v[i] += x;return;}

	int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += v[i];return res;}

}

struct query

{

	int l,r,id;

}q[MAXM];

int ans[MAXM];

bool cmp_r(query a,query b){return a.r < b.r;}

#define MOD 1000000007

int main()

{

	n = rd();m = rd();

	PAM::init();

	scanf("%s",c + 1);

	for(int i = 1;i <= n;++i)PAM::pos[i] = PAM::extend(i,c[i] - 'a');

	PAM::build();PAM::dfs(1);

	for(int i = 1;i <= m;++i)

	{

		q[i].l = rd();q[i].r = rd();

		q[i].id = i;

	}

	sort(q + 1,q + 1 + m,cmp_r);

	ST::build(ST::root,1,PAM::ptr);

	for(int i = 1,j = 1;i <= n;++i)

	{

		for(int k = PAM::pos[i];k != 0;k = PAM::t[PAM::nxt[k]].fail)

		{

			BIT::add(max(ST::query(ST::root,PAM::ind[k],PAM::oud[k],1,PAM::ptr) - PAM::t[k].len + 2,1),1);

			BIT::add(i - PAM::t[PAM::nxt[k]].len + 2,-1);

		}

		ST::change(ST::root,PAM::ind[PAM::pos[i]],i,1,PAM::ptr);

		while(j <= m && q[j].r == i)

		{

			ans[q[j].id] = BIT::query(q[j].l);

			++j;

		}

	}

	int res = 0;

	for(int i = 1;i <= m;++i)

	{

		res = (res + 1ll * ans[i] * i) % MOD;

	}

	cout << res << endl;

	return 0;

}