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
#include<bits/stdc++.h>
using namespace std;

#define fwd(i, a, b) for(int i=(a);i<(int)(b);i++)
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(X) (X).begin(), (X).end()
#define sz(X) ((int)(X).size())
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

template <int32_t _MODD>
    struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<_MODD> operator + (modint<_MODD> other) const { int32_t c = this->value + other.value; return modint<_MODD>(c >= _MODD ? c - _MODD : c); }
    inline modint<_MODD> operator - (modint<_MODD> other) const { int32_t c = this->value - other.value; return modint<_MODD>(c <	0 ? c + _MODD : c); }
    inline modint<_MODD> operator * (modint<_MODD> other) const { int32_t c = (int64_t)this->value * other.value % _MODD; return modint<_MODD>(c < 0 ? c + _MODD : c); }
    inline modint<_MODD> & operator += (modint<_MODD> other) { this->value += other.value; if (this->value >= _MODD) this->value -= _MODD; return *this; }
    inline modint<_MODD> & operator -= (modint<_MODD> other) { this->value -= other.value; if (this->value <	0) this->value += _MODD; return *this; }
    inline modint<_MODD> & operator *= (modint<_MODD> other) { this->value = (int64_t)this->value * other.value % _MODD; if (this->value < 0) this->value += _MODD; return *this; }
    inline modint<_MODD> operator - () const { return modint<_MODD>(this->value ? _MODD - this->value : 0); }
    modint<_MODD> pow(uint64_t k) const {
        modint<_MODD> x = *this, y = 1;
        for (; k; k >>= 1) {
        if (k & 1) y *= x;
        x *= x;
        }
        return y;
    }
    modint<_MODD> inv() const { return pow(_MODD - 2); }  // _MODD must be a prime
    inline modint<_MODD> operator /  (modint<_MODD> other) const { return *this *  other.inv(); }
    inline modint<_MODD> operator /= (modint<_MODD> other)	   { return *this *= other.inv(); }
    inline bool operator == (modint<_MODD> other) const { return value == other.value; }
    inline bool operator != (modint<_MODD> other) const { return value != other.value; }
    inline bool operator < (modint<_MODD> other) const { return value < other.value; }
    inline bool operator > (modint<_MODD> other) const { return value > other.value; }
    };
    template <int32_t _MODD> modint<_MODD> operator * (int64_t value, modint<_MODD> n) { return modint<_MODD>(value) * n; }
    template <int32_t _MODD> modint<_MODD> operator * (int32_t value, modint<_MODD> n) { return modint<_MODD>(value % _MODD) * n; }
    template <int32_t _MODD> istream & operator >> (istream & in, modint<_MODD> &n) { return in >> n.value; }
    template <int32_t _MODD> ostream & operator << (ostream & out, modint<_MODD> n) { return out << n.value; }

typedef modint<(int)(1e9+7)> mint;


mint numberOfSeqsOfLengthNOverPlusMinus1HavingSumMod3DifferentThanR(int n, int r) {
    mint res = (mint(2).pow(n)-mint(n%2 == 0 ? 1 : 2))/mint(3);
    static const vector<vi> lookup = {
        {1,0,0},
        {1,1,0},
        {0,1,0},
        {0,1,1},
        {0,0,1},
        {1,0,1}
    };
    return mint(2).pow(n) - (res + mint(lookup[n%6][r]));
}

int cntC[2], cntZ[2], cntN;

void update(char c, int pos, int v) {
    if(c == 'C')
        cntC[pos&1] += v;
    else if(c == 'Z')
        cntZ[pos&1] += v;
    else
        cntN += v;
}

bool czczPossible() {
    return cntC[1] == 0 && cntZ[0] == 0;
}

bool zczcPossible() {
    return cntC[0] == 0 && cntZ[1] == 0;
}

int n;
void ans() {
    int sum = (cntC[0]+cntC[1]-cntZ[0]-cntZ[1]);
    int badR = 2*(cntN-sum);
    badR = (badR%3+3)%3;
    mint res = numberOfSeqsOfLengthNOverPlusMinus1HavingSumMod3DifferentThanR(cntN, badR);
    if(czczPossible() && n%2 == 1) 
        res -= 1;
    if(zczcPossible() && n%2 == 1) 
        res -= 1;

    if(n == 1) 
        res = mint(cntN == 0 ? 1 : 2);
    
    cout<<res<<"\n";
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin >> n >> q;
    string s;
    cin >> s;
    rep(i,n)
        update(s[i],i,1);

    ans();
    while(q--) {
        int pos; char c;
        cin >> pos >> c;
        pos--;
        update(s[pos], pos, -1);
        s[pos] = c;
        update(s[pos], pos, 1);
        ans();
    }
}