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
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
long long dp[200005][3];
int cnt[2];
int a, t;
string d;
int n_cnt = 0, sum = 0;
int f(char c)
{
    if(c == 'C')
        return 1;
    if(c == 'Z')
        return 2;
}
void pre()
{
    dp[0][0] = 1;
    for(int x = 1; x <= 200000; x++)
        for(int y=0;y<3;y++)
            dp[x][y] = (dp[x-1][0] + dp[x-1][1] + dp[x-1][2] - dp[x-1][y]) % mod;
}
void ins_letter(int i, int val)
{
    if(d[i] == 'N')
        n_cnt += val;
    else
    {
        cnt[(i + f(d[i])) % 2] += val;
        sum += f(d[i]) * val;
    }
}
void ans()
{
    if(a == 1)
    {
        if(n_cnt == 1)
            cout<<2<<'\n';
        else
            cout<<1<<'\n';
        return;
    }
    long long res;
    if(sum % 3 == 0)
        res = dp[n_cnt][1] + dp[n_cnt][2];
    if(sum % 3 == 1)
        res = dp[n_cnt][0] + dp[n_cnt][1];
    if(sum % 3 == 2)
        res = dp[n_cnt][0] + dp[n_cnt][2];
    if(a % 2 == 1)
    {
        if(cnt[0] == 0)
            res--;
        if(cnt[1] == 0)
            res--;
    }
    cout<<(res + mod) % mod << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	pre();
	cin>>a>>t>>d;
	for(int i=0;i<a;i++)
        ins_letter(i, 1);
    ans();
    while(t--)
    {
        int c;
        char e;
        cin>>c>>e;
        c--;
        ins_letter(c, -1);
        d[c] = e;
        ins_letter(c, 1);
        ans();
    }
	return 0;
}