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


using namespace std;


using ll = long long int;

const ll MOD = 1000000007;
const ll INV3 = 333333336;

const int MAXN = 200010;



template<ll MOD>
struct Zp {
  ll a;

  Zp(ll _a) {
    a = _a % MOD;
    if (a < 0) a += MOD;
  }
};

template<ll MOD>
Zp<MOD> operator+(const Zp<MOD> &l, const Zp<MOD> &r) {
  return Zp<MOD>(l.a + r.a);
}

template<ll MOD>
Zp<MOD> operator-(const Zp<MOD> &l, const Zp<MOD> &r) {
  return Zp<MOD>(l.a - r.a);
}

template<ll MOD>
Zp<MOD> operator*(const Zp<MOD> &l, const Zp<MOD> &r) {
  return Zp<MOD>(l.a * r.a);
}

template<ll MOD>
Zp<MOD> pow(const Zp<MOD> &a, int w) {
  if (w == 0) return Zp<MOD>(1);
  if (w % 2 == 0) {
    Zp<MOD> b = pow(a, w / 2);
    return b * b;
  }
  return a * pow(a, w - 1);
}




// sum of n choose i over (i = k mod 3)
Zp<MOD> newt3(int n, int k) {
  Zp<MOD> pow2 = pow(Zp<MOD>(2), n);
  Zp<MOD> pow2mod3(n % 2 == 0 ? 1 : 2);
  Zp<MOD> pow2div3 = (pow2 - pow2mod3) * Zp<MOD>(INV3);

  return pow2div3 + Zp<MOD>((k % 3 == (2 * n) % 3) == (n % 2 == 0) ? 1 : 0);
}

// string can be decomposed iff
//  - it is not of the form XYXYXYX... and
//  - (number of C - number of Z) mod 3 != 0
ll out(int n, int nZ0, int nZ1, int nC0, int nC1, int nN) {
  int k = (2 * (nN + nZ0 + nZ1 - nC0 - nC1)) % 3;
  if (k < 0) k += 3;

  Zp<MOD> o = newt3(nN, (k + 1) % 3) + newt3(nN, (k + 2) % 3);
  if (nZ0 == 0 && nC1 == 0 && n % 2 == 1 && n > 1) o = o - Zp<MOD>(1);
  if (nZ1 == 0 && nC0 == 0 && n % 2 == 1 && n > 1) o = o - Zp<MOD>(1);
  return o.a;
}

void addContrib(int sign, int p, char c, int &nZ0, int &nZ1, int &nC0, int &nC1, int &nN) {
  if (c == 'C') {
    if (p % 2 == 0) nC0 += sign;
    else nC1 += sign;
  }
  if (c == 'Z') {
    if (p % 2 == 0) nZ0 += sign;
    else nZ1 += sign;
  }
  if (c == 'N') nN += sign;
}



char S[MAXN];

int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  scanf(" %s", S + 1);

  int nZ0 = 0, nZ1 = 0, nC0 = 0, nC1 = 0, nN = 0;
  for (int i = 1; i <= n; i++) {
    addContrib(1, i, S[i], nZ0, nZ1, nC0, nC1, nN);
  }

  printf("%lld\n", out(n, nZ0, nZ1, nC0, nC1, nN));
  for (int i = 0; i < q; i++) {
    int p; char c;
    scanf("%d %c", &p, &c);
    addContrib(-1, p, S[p], nZ0, nZ1, nC0, nC1, nN);
    S[p] = c;
    addContrib(+1, p, S[p], nZ0, nZ1, nC0, nC1, nN);
    printf("%lld\n", out(n, nZ0, nZ1, nC0, nC1, nN));
  }
}