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
#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
char s[200005];
int jc[200005],njc[200005];
int dp[200005][3];
int ksm(int n,int k)
{
	int ans=1;
	while(k>=1)
	{
		if(k&1)ans=1LL*ans*n%mod;
		k>>=1;
		n=1LL*n*n%mod;
	}
	return ans;
}
int sla=0,slb=0,sln=0,nh=0;
void del(int x)
{
	if(x%2==0&&s[x]=='Z')sla--;
	if(x%2==1&&s[x]=='C')sla--;
	if(x%2==0&&s[x]=='C')slb--;
	if(x%2==1&&s[x]=='Z')slb--;
	if(s[x]=='N')sln--;
	if(s[x]=='C')nh=(nh+2)%3;
	if(s[x]=='Z')nh=(nh+1)%3;
}
void ins(int x)
{
	if(x%2==0&&s[x]=='Z')sla++;
	if(x%2==1&&s[x]=='C')sla++;
	if(x%2==0&&s[x]=='C')slb++;
	if(x%2==1&&s[x]=='Z')slb++;
	if(s[x]=='N')sln++;
	if(s[x]=='C')nh=(nh+1)%3;
	if(s[x]=='Z')nh=(nh+2)%3;
}
int cm[200005];
int main()
{
	int n,q;
	n=read();
	q=read();
	scanf("%s",s+1);
	jc[0]=1;
	for(int i=1;i<=n;i++)jc[i]=1LL*i*jc[i-1]%mod;
	njc[n]=ksm(jc[n],mod-2);
	for(int i=n-1;i>=0;i--)njc[i]=1LL*(i+1)*njc[i+1]%mod;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=2;j++)
		{
			dp[i][(j+1)%3]=(dp[i][(j+1)%3]+dp[i-1][j])%mod;
			dp[i][(j+2)%3]=(dp[i][(j+2)%3]+dp[i-1][j])%mod;
		}
	}
	cm[0]=1;
	for(int i=1;i<=n;i++)cm[i]=2LL*cm[i-1]%mod;
	for(int i=1;i<=n;i++)
	{
		ins(i);
	}
	int x,y;
	int ans=cm[sln];
	ans=(ans+mod-dp[sln][(3-nh)%3])%mod;
	if(n%2==1&&sla==0)ans=(ans+mod-1)%mod;
	if(n%2==1&&slb==0)ans=(ans+mod-1)%mod;
	printf("%d\n",ans);
	for(int i=1;i<=q;i++)
	{
		x=read();
		y=getchar();
		while(y<'A'||y>'Z')y=getchar();
		del(x);
		s[x]=y;
		ins(x);
		int ans=cm[sln];
		ans=(ans+mod-dp[sln][(3-nh)%3])%mod;
		if(n%2==1&&sla==0)ans=(ans+mod-1)%mod;
		if(n%2==1&&slb==0)ans=(ans+mod-1)%mod;
		printf("%d\n",ans);
	}
}