In this indifferent world, light crying

For a substring $abc$, It is easy to find the front $i$ Number of bit sequences , Write it down as $dp[i][a][b][c]$
For a substring $ab$, It is easy to find the front $i$ Number of bit sequences , Write it down as $dp[i][a][b]$
For a substring $a$, It is easy to find the front $i$ Number of bit sequences , Write it down as $dp[i][a]$

First consider $dp[r][a][b][c]-dp[l-1][a][b][c]$, The number of sequences obtained in this way is two more .

The first category is $bc$ stay $[l,r]$ Inside ,$a$ stay $[1,l-1]$ Inside
$[l,r]$ Internal $bc$ The number of sequences is $dp[r][a][b]-dp[l-1][a][b]-(dp[r][b]-dp[l-1][b])\times dp[l-1][a]$
The number of the first category is
$$(dp[r][a][b]-dp[l-1][a][b]-(dp[r][b]-dp[l-1][b])\times dp[l-1][a])\times dp[l-1][a]$$
The second type is $c$ stay $[l,r]$ Inside ,$ab$ stay $[1,l-1]$ Inside
The number of
$$(dp[c][r]-dp[c][l-1])\times dp[a][b][l-1]$$
The final answer is
$$dp[r][a][b][c]-dp[l-1][a][b][c]-((dp[r][a][b]-dp[l-1][a][b]-(dp[r][b]-dp[l-1][b])\times dp[l-1][a])\times dp[l-1][a])-((dp[c][r]-dp[c][l-1])\times dp[a][b][l-1])$$
be aware $dp[n][a][b][c]$ It can be used $O(n\times 26^2)$ Complexity of complete （ Use the end point to optimize one dimension ）, We can ask each group of answers offline $O(n\times 26^2+q\times C)$ complete

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    
    int pos;
    ll val;
};
struct query
{
    
    int len,pos,id,f,a,b,c;
};
vector<query>v[80005];

ll Q[500005][8];

ll presum[26][26][26];
ll dp[26][26][3];
char ss[4];
char s[80005];
int main()
{
    
    int n,q;
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    for(int i=1;i<=q;i++)
    {
    
// printf("q=%d\n",q);
        int l,r;
        scanf("%d%d",&l,&r);
        scanf("%s",ss+1);
// printf("q=%d\n",q);
        ///  The length is 3 And 
        v[l-1].push_back({
    3,5,i,-1,ss[1]-'a',ss[2]-'a',ss[3]-'a'});
        v[r].push_back({
    3,5,i,1,ss[1]-'a',ss[2]-'a',ss[3]-'a'});
        /// front 2  Back 1

        v[l-1].push_back({
    2,1,i,1,ss[1]-'a',ss[2]-'a',ss[3]-'a'});

        v[r].push_back({
    1,2,i,1,ss[3]-'a',0,0});
        v[l-1].push_back({
    1,2,i,-1,ss[3]-'a',0,0});

        /// front 1  Back 2

        v[l-1].push_back({
    1,3,i,1,ss[1]-'a',ss[2]-'a',ss[3]-'a'});

        v[r].push_back({
    2,4,i,1,ss[2]-'a',ss[3]-'a',0});
        v[l-1].push_back({
    2,4,i,-1,ss[2]-'a',ss[3]-'a',0});

        v[r].push_back({
    1,6,i,1,ss[3]-'a',0,0});
        v[l-1].push_back({
    1,6,i,-1,ss[3]-'a',0,0});

        v[l-1].push_back({
    1,7,i,1,ss[2]-'a',0,0});
// printf("q=%d\n",q);
    }

    for(int j=0;j<=25;j++)
        for(int k=0;k<=25;k++)dp[j][k][0]=1;
    for(int i=1;i<=n;i++)
    {
    

        for(int j=0;j<=25;j++)
        for(int k=0;k<=25;k++)
        {
    
            presum[j][k][s[i]-'a']+=dp[j][k][2];
            if(s[i]-'a'==k)dp[j][k][2]+=dp[j][k][1];
            if(s[i]-'a'==j)dp[j][k][1]+=dp[j][k][0];
        }
        for(auto [len,pos,id,f,a,b,c]:v[i])
        {
    
// printf("len=%d pos=%d id=%d f=%d a=%d b=%d c=%d \n",len,pos,id,f,a,b,c);
            if(len==1)Q[id][pos]+=f*dp[a][0][1];
            else if(len==2)Q[id][pos]+=f*dp[a][b][2];
            else if(len==3)Q[id][pos]+=f*presum[a][b][c];
        }
    }
    for(int i=1;i<=q;i++)printf("%lld\n",Q[i][5]-Q[i][1]*Q[i][2]-Q[i][3]*(Q[i][4]-Q[i][6]*Q[i][7]));

    return 0;
}