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
//Jakub Nowak XIV LO Wroclaw
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 2e5+7, mod = 1e9+7, x3 = 3e6;//x3 = duza wielokrotnosc 3
int n, q;//n<=2e5; q<=1e5
string S;
int nieb, ziel, czer, cp, zp;//odp = (dp[nieb][(czer-ziel+1+3e6)%3]+dp[nieb][(czer-ziel-1+3e6)%3]-(cp==0&&zp==ziel)-(cp==czer&&zp==0)+mod)%mod;
int dp[N][3]={1};//dp[k][r] = liczba kombinacji doboru wartosci zbioru k niebieskich, tak aby roznica w nim wynosila r (mod 1e9+7)

void dodaj(int i) {
    if(S[i]=='N') nieb++;
    if(S[i]=='Z') ziel++, zp+=!(i%2);
    if(S[i]=='C') czer++, cp+=!(i%2);
}

void usun(int k) {
    if(S[k]=='N') nieb--;
    if(S[k]=='Z') ziel--, zp-=!(k%2);
    if(S[k]=='C') czer--, cp-=!(k%2);
}

int odp() {
    return (dp[nieb][(czer-ziel+1+x3)%3]+dp[nieb][(czer-ziel-1+x3)%3]-(cp==0&&zp==ziel&&(n%2)==1&&n!=1)-(cp==czer&&zp==0&&(n%2)==1&&n!=1)+mod)%mod;
}

void deb() {
    cout<<"\n------deb-----\n";
    cout<<"Slowo: "<<S<<"\n";
    cout<<"Z; C; N: "<<ziel<<"; "<<czer<<"; "<<nieb<<"\n";
    cout<<"CP; ZP: "<<cp<<"; "<<zp<<"\n";
    cout<<"Czy zielone na parzystych, czerwone na nieparzystych: "<<(cp==0&&zp==ziel)<<"\n";
    cout<<"Czy czerwone na parzystych, zielone na nieparzystych: "<<(cp==czer&&zp==0)<<"\n";
    cout<<"Wynik: ";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++) {//liczenie dp
        for(int r=0; r<3; r++) dp[i][r]=(dp[i-1][(r+2)%3]+dp[i-1][(r+1)%3])%mod;
    }
    cin>>S;
    for(int i=0; i<S.size(); i++) {
        dodaj(i);
    }
    //odp = (dp[nieb][(czer-ziel+1+x3)%3]+dp[nieb][(czer-ziel-1+x3)%3]-(cp==0&&zp==ziel)-(cp==czer&&zp==0)+mod)%mod;//co gdy opcja z np nie jest dobra?
    //deb();
    cout<<odp()<<"\n";
    for(int i=1; i<=q; i++) {
        int k;
        char ch;
        cin>>k>>ch;
        usun(k-1);
        S[k-1]=ch;
        dodaj(k-1);
        //odp = (dp[nieb][(czer-ziel+1+x3)%3]+dp[nieb][(czer-ziel-1+x3)%3]-(cp==0&&zp==ziel)-(cp==czer&&zp==0)+mod)%mod;
        //deb();
        cout<<odp()<<"\n";
    }
}