http://www.lydsy.com/JudgeOnline/upload/Noi2017D1.pdf

# include <iostream>

# include <cstdio>

# include <vector>

# include <cstring>

using namespace std;

typedef unsigned long long llu;

const int N = 5e5 + ;

const int M =  << ;

const int mod = ;

const llu bac = ;

int n,m,a[N],hs[M + ],mx,q[N][],nex[N],pre[N];

llu id[M + ],pw[],t[M + ];

char str[M + ];

vector<llu>Q[N];

int read()

{

    int x = ;char i = getchar();

    while(!isdigit(i))i = getchar();

    while(isdigit(i))x = x *  + i - '',i = getchar();

    return x;

}

int ins(llu s)

{

    int u = s % M;

    while(id[u])

    {

      if(id[u] == s)return u;

      u = (u + ) & (M - );

    }

    id[u] = s;

    return  u;

}

bool add(llu s,int x)

{

    int u = s % M;

    while(id[u])

    {

        if(id[u] == s)return hs[u] += x;

        u = (u + ) & (M - );

    }

    return ;

}

int lc[],rc[],lx,rx,p;llu g[];

void solve(int x,int y,int d)

{

    lx = rx = p = ;

    for(int i = ,u = x;i < mx && u;i++,u = pre[u])lc[++lx] = a[u];

    for(int i = ,u = y;i < mx && u;i++,u = nex[u])rc[++rx] = a[u];

    for(int i = lx;i >= ;i--)g[++p] = lc[i];

    for(int i = ;i <= rx;i++)g[++p] = rc[i];

    for(int i = ;i <= p;i++)g[i] = g[i - ] * bac + g[i];

    for(int i = ;i < lx;i++)

    {

        int r = min(i + mx,p);

        for(int j = lx + ;j <= r;j++)

        add(g[j] - g[i] * pw[j - i],d);

    }

}

int main()

{

    pw[] = ;for(int i = ;i <= ;i++)pw[i] = pw[i - ] * bac;

    n = read();m = read();

    for(int i = ;i <= n;i++)a[i] = read();

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

    {

        q[i][] = read();

        if(q[i][] == )q[i][] = read(),q[i][] = read();

        else if(q[i][] == )q[i][] = read();

        else

        {

            scanf("%s",str + );int len = strlen(str + );

            int k  = read();

            mx = max(mx,k);

            for(int j = ;j <= len;j++)t[j] = t[j - ] * bac + str[j] - '';

            for(int j = k;j <= len;j++)

            Q[i].push_back(ins(t[j] - t[j - k] * pw[k]));

        }

    }

    for(int i = ;i <= n;i++)add(a[i],);

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

    {

        int x,y;

        if(q[i][] == )

        {

            x = q[i][];y = q[i][];

            nex[x] = y;pre[y] = x;

            solve(x,y,);

        }

        else if(q[i][] == )

        {

           x = q[i][];y = nex[x];

           nex[x] = pre[y] = ;

           solve(x,y,-);

        }

        else

        {

            llu ans = ;

            for(int j = ;j < Q[i].size();j++)

            ans = ans * (llu)hs[Q[i][j]] % mod;

            printf("%d\n",(int)ans);

        }

    }

}