rt，心态要炸了

#include <iostream>
#include <cstdio>
#include <map>
#include <ctime>
#include <cstdlib> 
#define int long long 
#define MOD 998244353
#define M 10000007

using namespace std;

int rnd[7];
int mp[M * 2];
int pre[1000001],nxt[1000001],S[1000001];
int op;
long long ans;
string s,nw;
char c[1000001],ls[1000001];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

signed main()
{
//	freopen( "e.in" , "r" , stdin );
//	freopen( "e1.out" , "w" , stdout );
	srand( time( 0 ) );
	for( int i = 1 ; i <= 6 ; i ++ )
		rnd[i] = rand() * rand() % M + 1;
	int n,T,x,y;
	cin >> n >> T;
	for( int i = 1 ; i <= n ; i ++ )
		cin >> c[i],pre[i] = nxt[i] = i,mp[rnd[c[i] - '0']] ++;
	while( T -- )
	{
		op = read();
		if( op == 1 )
		{
			x = read(),y = read();
			pre[y] = x;
			nxt[x] = y;
			for( int k = 2 ; k <= 50 ; k ++ )
			{
				nw = "";
				int cnt,d,len,sum = 0;
				cnt = 1;
				d = nxt[x];
				do
				{
					d = pre[d];
					nw = c[d] + nw;
					cnt ++;
				}
				while( cnt < k && pre[d] != d );
				cnt = 1;
				d = pre[y];
				do
				{
					d = nxt[d];
					nw = nw + c[d];
					cnt ++;
				}
				while( cnt < k && nxt[d] != d );
//				cout << k << ' ' << nw << endl;
				len = nw.size();
				S[0] = rnd[nw[0] - '0'];
				for( int i = 1 ; i < len ; i ++ )
					S[i] = ( S[i - 1] + rnd[nw[i] - '0'] ) % M;
				for( int i = 0 ; i < k - 1 ; i ++ )
					sum = ( sum + rnd[nw[i] - '0'] * ( i + 1 ) % M ) % M;
				for( int i = k - 1 ; i < len ; i ++ )
				{
					sum = ( sum + rnd[nw[i] - '0'] * k % M ) % M;
					mp[sum] = ( mp[sum] + 1 ) % MOD;
					sum = ( ( sum - S[i] + S[i - k] ) % M + M ) % M;
				}
			}
//			cout << endl; 
		} 
		if( op == 2 )
		{
			x = read();
			y = nxt[x];
			for( int k = 2 ; k <= 50 ; k ++ )
			{
				nw = "";
				int cnt,d,len,sum = 0;
				cnt = 1;
				d = nxt[x];
				do
				{
					d = pre[d];
					nw = c[d] + nw;
					cnt ++;
				}
				while( cnt < k && pre[d] != d );	
				cnt = 1;
				d = pre[y];
				do
				{
					d = nxt[d];
					nw = nw + c[d];
					cnt ++;
				}
				while( cnt < k && nxt[d] != d );
//				cout << k << ' ' << nw << endl;
				len = nw.size();
				S[0] = rnd[nw[0] - '0'];
				for( int i = 1 ; i < len ; i ++ )
					S[i] = ( S[i - 1] + rnd[nw[i] - '0'] ) % M;
				for( int i = 0 ; i < k - 1 ; i ++ )
					sum = ( sum + rnd[nw[i] - '0'] * ( i + 1 ) % M ) % M;
				for( int i = k - 1 ; i < len ; i ++ )
				{
					sum = ( sum + rnd[nw[i] - '0'] * k % M ) % M;
					mp[sum] = ( ( mp[sum] - 1 ) % MOD + MOD ) % MOD;
					sum = ( ( sum - S[i] + S[i - k] ) % M + M ) % M;
				}
			}
			nxt[x] = x;
			pre[y] = y;
//			cout << endl;
		}
		if( op == 3 )
		{
			int k,sum = 0;
			scanf( "%s" , &ls );
			s = ls;
			k = read();
			ans = 1;
			int len = s.size();
			S[0] = rnd[s[0] - '0'];
			for( int i = 1 ; i < len ; i ++ )
				S[i] = ( S[i - 1] + rnd[s[i] - '0'] ) % M;
			for( int i = 0 ; i < k - 1 ; i ++ )
				sum = ( sum + rnd[s[i] - '0'] * ( i + 1 ) % M ) % M;
			for( int i = k - 1 ; i < len ; i ++ )
			{
				sum = ( sum + rnd[s[i] - '0'] * k % M ) % M;
				ans = ans * mp[sum] % MOD;
//				cout << i << ' ' << sum << ' ' << mp[sum] << endl;
				sum = ( ( sum - S[i] + S[i - k] ) % M + M ) % M;
			}
			printf( "%d\n" , ans );
		}
	}
	return 0;
}