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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Jakub Rozek
// Wielki Zderzacz Termionoow
// PA 2022 A r1
// czas: n + q
// pami: n

#include "bits/stdc++.h"
using namespace std;

const int N=200005;
const long long mod=1000000007;

long long n,q,x,czerwone,zielone,niebieskie,czerwoneparzyste,zieloneparzyste;
string s;
char znak;
long long odwrotnosc3,pierwszyzly;
long long pot2[N];
long long wartosccos[3][6];

long long co3napietrze(int a, int b)
{
    long long odp=pot2[a]+mod+wartosccos[b][a%6];
    odp%=mod;
    odp*=odwrotnosc3;
    odp%=mod;
    return odp;
}

long long licz()
{
    if(n==1)
    {
        if(s[1]=='N') return 2;
        else return 1;
    }

    long long odp=pot2[niebieskie]+mod-co3napietrze(niebieskie, (pierwszyzly + 3 - czerwone%3)%3 );
    odp%=mod;
    
    if(n%2)
    {
        odp+=mod;
        if(czerwoneparzyste==czerwone && zieloneparzyste==0) --odp;
        if(czerwoneparzyste==0 && zieloneparzyste==zielone) --odp;
        odp%=mod;
    }
    
    return odp;
}

void preprocesing()
{
    //potegi 2
    pot2[0]=1;
    for(long long i=1; i<N; ++i)
        pot2[i]=(pot2[i-1]*2)%mod;
    
    //co3od0
    wartosccos[0][0]=2;
    wartosccos[0][1]=1;
    wartosccos[0][2]=-1;
    wartosccos[0][3]=-2;
    wartosccos[0][4]=-1;
    wartosccos[0][5]=1;
    //co3od1
    wartosccos[1][0]=-1;
    wartosccos[1][1]=1;
    wartosccos[1][2]=2;
    wartosccos[1][3]=1;
    wartosccos[1][4]=-1;
    wartosccos[1][5]=-2;
    //co3od2
    wartosccos[2][0]=-1;
    wartosccos[2][1]=-2;
    wartosccos[2][2]=-1;
    wartosccos[2][3]=1;
    wartosccos[2][4]=2;
    wartosccos[2][5]=1;
    
    //odwrotnosc3
    odwrotnosc3=333333336;

    //pierwszyzly;
    if(n%3==0) pierwszyzly=0;
    if(n%3==1) pierwszyzly=2;
    if(n%3==2) pierwszyzly=1;
}

void ustawznak(int a, int w)
{
    if(s[a]=='C') czerwone+=w;
    if(s[a]=='Z') zielone+=w;
    if(s[a]=='N') niebieskie+=w;
    if(a%2==0)
    {
        if(s[a]=='C') czerwoneparzyste+=w;
        if(s[a]=='Z') zieloneparzyste+=w;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>q>>s;
    s="#"+s;

    preprocesing();
    
    for(int i=1; i<=n; ++i) ustawznak(i,1);

    cout<<licz()<<"\n";
    while(q--)
    {
        cin>>x>>znak;
        ustawznak(x,-1);
        s[x]=znak;
        ustawznak(x,1);
        cout<<licz()<<"\n";
    }
    
    return 0;
}