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
125
126
/* -----------------------
Autor: Tomasz Boguslawski
-------------------------- */
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<string>
#include<sstream>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include <fstream>
#include<math.h>

#define LL long long
#define FOR(x, b, e) for(LL x = b; x <= (e); x++)
#define FORS(x, b, e, s) for(LL x = b; x <= (e); x+=s)
#define FORD(x, b, e) for(LL x = b; x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG if (debug)
#define MIN(a,b) ((a>b)?b:a)
#define MAX(a,b) ((a>b)?a:b)

using namespace std;

const LL mo = 1000000007;

class V
{
public:
    LL v[10];
    V() {};
    void init(char c)
    {
        FOR(i,0,9) v[i]=0;
        if (c=='Z') v[1]=1;
        else if (c=='C') v[2]=1;
        else if (c=='N') { v[1]=1; v[2]=1; };
    }
    void init0() { v[0]=1; FOR(i,1,9) v[i]=0; };
    inline void makeSum(V& v1, V& v2)
    {
        v[0]=(v1.v[0]*v2.v[0])%mo;
        v[1]=(v1.v[0]*v2.v[1])%mo + (v1.v[1]*v2.v[0])%mo;
        v[2]=(v1.v[0]*v2.v[2])%mo + (v1.v[2]*v2.v[0])%mo;
        v[3]=(v1.v[0]*v2.v[3])%mo + (v1.v[1]*v2.v[5])%mo + (v1.v[3]*v2.v[0])%mo + (v1.v[3]*v2.v[5])%mo + (v1.v[4]*v2.v[1])%mo + (v1.v[4]*v2.v[3])%mo;
        v[4]=(v1.v[0]*v2.v[4])%mo + (v1.v[1]*v2.v[2])%mo + (v1.v[1]*v2.v[6])%mo + (v1.v[3]*v2.v[2])%mo + (v1.v[3]*v2.v[6])%mo + (v1.v[4]*v2.v[0])%mo + (v1.v[4]*v2.v[4])%mo;
        v[5]=(v1.v[0]*v2.v[5])%mo + (v1.v[2]*v2.v[1])%mo + (v1.v[2]*v2.v[3])%mo + (v1.v[5]*v2.v[0])%mo + (v1.v[5]*v2.v[5])%mo + (v1.v[6]*v2.v[1])%mo + (v1.v[6]*v2.v[3])%mo;
        v[6]=(v1.v[0]*v2.v[6])%mo + (v1.v[2]*v2.v[4])%mo + (v1.v[5]*v2.v[2])%mo + (v1.v[5]*v2.v[6])%mo + (v1.v[6]*v2.v[0])%mo + (v1.v[6]*v2.v[4])%mo;
        v[7]=(v1.v[0]*v2.v[7])%mo + (v1.v[1]*v2.v[4])%mo + (v1.v[1]*v2.v[9])%mo + (v1.v[2]*v2.v[2])%mo + (v1.v[2]*v2.v[6])%mo + (v1.v[2]*v2.v[8])%mo + (v1.v[3]*v2.v[4])%mo + (v1.v[3]*v2.v[9])%mo + (v1.v[4]*v2.v[7])%mo + (v1.v[5]*v2.v[1])%mo + (v1.v[5]*v2.v[3])%mo + (v1.v[5]*v2.v[7])%mo + (v1.v[6]*v2.v[2])%mo + (v1.v[6]*v2.v[6])%mo + (v1.v[6]*v2.v[8])%mo + (v1.v[7]*v2.v[0])%mo + (v1.v[7]*v2.v[4])%mo + (v1.v[7]*v2.v[5])%mo + (v1.v[7]*v2.v[9])%mo + (v1.v[8]*v2.v[2])%mo + (v1.v[8]*v2.v[6])%mo + (v1.v[8]*v2.v[8])%mo + (v1.v[9]*v2.v[1])%mo + (v1.v[9]*v2.v[3])%mo + (v1.v[9]*v2.v[7])%mo;
        v[8]=(v1.v[0]*v2.v[8])%mo + (v1.v[1]*v2.v[1])%mo + (v1.v[1]*v2.v[3])%mo + (v1.v[1]*v2.v[7])%mo + (v1.v[2]*v2.v[5])%mo + (v1.v[2]*v2.v[9])%mo + (v1.v[3]*v2.v[1])%mo + (v1.v[3]*v2.v[3])%mo + (v1.v[3]*v2.v[7])%mo + (v1.v[4]*v2.v[2])%mo + (v1.v[4]*v2.v[6])%mo + (v1.v[4]*v2.v[8])%mo + (v1.v[5]*v2.v[8])%mo + (v1.v[6]*v2.v[5])%mo + (v1.v[6]*v2.v[9])%mo + (v1.v[7]*v2.v[1])%mo + (v1.v[7]*v2.v[3])%mo + (v1.v[7]*v2.v[7])%mo + (v1.v[8]*v2.v[0])%mo + (v1.v[8]*v2.v[4])%mo + (v1.v[8]*v2.v[5])%mo + (v1.v[8]*v2.v[9])%mo + (v1.v[9]*v2.v[2])%mo + (v1.v[9]*v2.v[6])%mo + (v1.v[9]*v2.v[8])%mo;
        v[9]=(v1.v[0]*v2.v[9])%mo + (v1.v[1]*v2.v[8])%mo + (v1.v[2]*v2.v[7])%mo + (v1.v[3]*v2.v[8])%mo + (v1.v[4]*v2.v[5])%mo + (v1.v[4]*v2.v[9])%mo + (v1.v[5]*v2.v[4])%mo + (v1.v[5]*v2.v[9])%mo + (v1.v[6]*v2.v[7])%mo + (v1.v[7]*v2.v[2])%mo + (v1.v[7]*v2.v[6])%mo + (v1.v[7]*v2.v[8])%mo + (v1.v[8]*v2.v[1])%mo + (v1.v[8]*v2.v[3])%mo + (v1.v[8]*v2.v[7])%mo + (v1.v[9]*v2.v[0])%mo + (v1.v[9]*v2.v[4])%mo + (v1.v[9]*v2.v[5])%mo + (v1.v[9]*v2.v[9])%mo;
        FOR(i,0,9) v[i]=v[i]%mo;
    };
    LL countGood()
    {
        return (v[1]+v[2]+v[7]+v[8])%mo;
    }
};

V tree[550000];
LL N, Q, firstIndex;

void buildTree(string &s, LL n)
{
    firstIndex = 1;
    LL levelSize = 1;
    while (levelSize<n)
    {
        firstIndex+=levelSize;
        levelSize*=2;
    }
    FOR(i,0,n-1) tree[firstIndex+i].init(s[i]);
    FOR(i,n,levelSize+1) tree[firstIndex+i].init0();
    FORD(k,firstIndex-1,1)
    {
        tree[k].makeSum(tree[k*2], tree[k*2+1]);
    }
}

void updateTree(LL pos)
{
    LL ch1, ch2;
    while (pos>1)
    {
        pos = pos / 2;
        ch1 = pos*2;
        ch2 = ch1+1;
        tree[pos].makeSum(tree[ch1], tree[ch2]);
    }
}

/// MAIN
int main(int argc, char* argv[])
{
    // magic formula, which makes streams work faster:
	ios_base::sync_with_stdio(0);

	cin >> N; cin >> Q;
	string ss;
	cin >> ss;
	buildTree(ss, N);
	cout << tree[1].countGood() << "\n";
	LL ind;
	string ch; char c;
	FOR(q,1,Q)
	{
	    cin >> ind;
	    cin >> ch; c=ch[0];
	    if (ss[ind-1]!=c)
        {
            ss[ind-1]=c;
            tree[firstIndex+ind-1].init(c);
            updateTree(firstIndex+ind-1);
        }
        cout << tree[1].countGood() << "\n";
	}
	return 0;
}