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
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
namespace debug { template <class c> struct rge { c b, e; }; template <class c> rge<c> range(c i, c j) { return rge<c>{i, j}; } template <class c> char spk(...); template <class c> auto spk(c* a) -> decltype(cerr << *a, 0); struct stream { ~stream() { cerr << endl; } template <class c> typename enable_if <sizeof spk<c>(0) != 1, stream&>::type operator<<(c i) { cerr << boolalpha << i; return *this; } template <class c> typename enable_if <sizeof spk<c>(0) == 1, stream&>::type operator<<(c i) { return *this << range(begin(i), end(i)); } template <class a, class b> stream& operator<<(pair <a,b> p) { return *this << "(" << p.first << ", " << p.second << ")"; } template <class c> stream& operator<<(rge<c> d) { *this << "["; for (auto it=d.b; it!=d.e; it++) *this << ", " + 2 * (it == d.b) << *it; return *this << "]"; } stream& _dbg(const string& s, int i, int b) { return *this; } template <class c, class ... cs> stream& _dbg(const string& s, int i, int b, c arg, cs ... args) { if (i == (int)(s.size())) return (*this << ": " << arg); b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{') - (s[i] == ')') - (s[i] == ']') - (s[i] == '}'); return (s[i] == ',' && b == 0) ? (*this << ": " << arg << "     ")._dbg(s, i + 1, b, args...) : (s[i] == ' ' ? *this : *this << s[i])._dbg(s, i + 1, b, arg, args...); } };}
#define dout debug::stream()
#define dbg(...) ((dout << ">> ")._dbg(#__VA_ARGS__, 0, 0, __VA_ARGS__))
#define f first
#define s second
#define sc scanf
#define pr printf
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define ss(x) ((int)((x).size()))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(b);i>=(a);i--)
#define upgrade cin.tie(0)->sync_with_stdio(0);
#define lowb(v,x) (lower_bound(all(v),(x))-v.begin())
#define uppb(v,x) (upper_bound(all(v),(x))-v.begin())
#define erase_duplicates(x) {sort(all(x));x.resize(unique(all(x))-x.begin());}
template <class p, class q> pair<p,q> operator-(pair<p,q> a, pair<p,q> b) { return mp(a.f - b.f, a.s - b.s); }
template <class p, class q> pair<p,q> operator+(pair<p,q> a, pair<p,q> b) { return mp(a.f + b.f, a.s + b.s); }
template <class p, class q> void umin(p &a, const q &b) { if (a > b) a = b; }
template <class p, class q> void umax(p &a, const q &b) { if (a < b) a = b; }
using lf=long double;
using ll=long long;
using cll=const ll;
using cint=const int;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //


const int mod = 1000000007;
const int N = 200005;
int n, q;
int cnt[1005][2];
int pw2[N];
int dp[N][3];
char t[N];


void answer()
{
	int cntC = cnt['C'][0] + cnt['C'][1];
	int cntZ = cnt['Z'][0] + cnt['Z'][1];
	int cntN = cnt['N'][0] + cnt['N'][1];
	
	int can1 = cnt['C'][0] == 0 && cnt['Z'][1] == 0;
	int can2 = cnt['C'][1] == 0 && cnt['Z'][0] == 0;

	int diff = (((cntC - cntZ) % 3) + 3) % 3;

	int ways = dp[cntN][diff];

	if (n == 1) { printf("%d\n", pw2[cntN]); return; }
	
	if (n % 2 == 1) ways += can1 + can2;
	
	ways = pw2[cntN] - ways;
	
	((ways %= mod) += mod) %= mod;
	
	printf("%d\n", ways);	
}

int main()
{
	scanf("%d%d", &n, &q);

	scanf("%s", t + 1);
	
	pw2[0] = 1;

	rep(i, 1, n) pw2[i] = 2 * pw2[i - 1] % mod;
	
	rep(i, 1, n) cnt[t[i]][i % 2] += 1;
	
	dp[0][0] = 1;

	rep(i, 0, n - 1) rep(j, 0, 2){
		(dp[i + 1][(j + 1) % 3] += dp[i][j]) %= mod;
		(dp[i + 1][(j + 2) % 3] += dp[i][j]) %= mod;
	}

	answer();

	while (q--){
		int pos;
		char val;
		scanf("%d %c", &pos, &val);
		cnt[t[pos]][pos % 2] -= 1;
		t[pos] = val;
		cnt[t[pos]][pos % 2] += 1;
		answer();
	}

	return 0;
}