1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;
int n,q,trans[1001],ile[3];
vector<int>tenieda;
char ciag[200001];
long long mod=1000000007,pot2[200001],odwmod3=333333336,dode=6000000000;
long long silnia[200001];
int cznaparz[2][2];
long long ileb[200001][3];
long long sp(long long podst,long long wyk)
{
	long long ret=1;
	while(wyk)
	{
		if(wyk&1)
			ret=(ret*podst)%mod;
		podst=(podst*podst)%mod;
		wyk>>=1;
	}
	return ret;
}
long long snwe(long long a,long long b)
{
	return (((silnia[a]*sp(silnia[b],mod-2))%mod)*sp(silnia[a-b],mod-2))%mod;
}
long long licz_wyn()
{
	long long uzysk=(6000000+ile[1]-ile[0]+ile[2])%6;
	if(uzysk%2!=0)
		return pot2[ile[2]];
	// cout<<ile[0]<<" "<<ile[1]<<" "<<ile[2]<<endl;	
	// cout<<uzysk<<endl;
	long long ret=ileb[ile[2]][uzysk/2];
	//cout<<ret<<endl;
	if(n&1)
	{
		if(ile[2]==n)
			ret+=2;
		else if((cznaparz[0][0]==0&&cznaparz[1][1]==0)||(cznaparz[0][1]==0&&cznaparz[1][0]==0))
			++ret;
	}
	ret%=mod;
	//cout<<ret<<endl;
	return (2*mod+pot2[ile[2]]-ret)%mod;
}
int main()
{
	trans['C']=0;
	trans['Z']=1;
	trans['N']=2;
	pot2[0]=1;
	silnia[0]=1;
	ileb[0][0]=1;
	for(int i=1;i<=200000;++i)
	{
		pot2[i]=(pot2[i-1]<<1)%mod;
		for(int j=0;j<3;++j)
			ileb[i][j]=(ileb[i-1][j]+ileb[i-1][(j+2)%3])%mod;
	}
	scanf("%d%d",&n,&q);
	if(n&1)
		ile[1]+=3;
	for(int i=n/2-(n&1);i>=0;i-=3)
		tenieda.push_back(i);
	getchar();
	for(int i=1;i<=n;++i)
	{
		ciag[i]=trans[getchar()];
		++ile[ciag[i]];
		if(ciag[i]!=2)
		cznaparz[ciag[i]][i%2]++;
	}
	if(n==1)
	{
		if(ciag[1]==2)
			printf("2\n");
		else
			printf("1\n");
	}
	else
		printf("%lld\n",licz_wyn());
	int a;
	char b;
	while(q)
	{
		--q;
		scanf("%d %c",&a,&b);
		b=trans[b];
		if(ciag[a]!=2)
			cznaparz[ciag[a]][a%2]--;
		--ile[ciag[a]];
		++ile[b];
		ciag[a]=b;
		if(b!=2)
			cznaparz[b][a%2]++;
		if(n==1)
		{
			if(b==2)
				printf("2\n");
			else
				printf("1\n");
		}
		else
		printf("%lld\n",licz_wyn());
	}
	return 0;
}