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
/*
    Zadanie: Wielki Zderzacz Termionów
    Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 7;
const int MOD = 1e9 + 7;

int dp[MAXN][6];
int cntN;
int cnt[2][2];
int n, q;
string s;

void update(char c, int i, int d)
{
    if (c == 'N')
        cntN += d;
    else
        cnt[c == 'Z'][i % 2] += d;
}

int result()
{
    if (n == 1) return 1 + (s[0] == 'N');
    int z = cnt[1][0] + cnt[1][1];
    int m = (((1 + 2*n - z) % 3) + 3) % 3;
    int res = dp[cntN][m];
    res = (res + dp[cntN][(m + 1) % 3]) % MOD;
    //cout << m << ' ' << res << '\n';
    if (cnt[1][0] == 0 && cnt[0][1] == 0 && ((m + z) % 3 == ((n / 2) % 3) || (m + 1 + z) % 3 == ((n / 2) % 3)))
        res = (res + MOD - 1) % MOD;
    if (cnt[1][1] == 0 && cnt[0][0] == 0 && ((m + z) % 3 == (((n + 1) / 2) % 3) || (m + 1 + z) % 3 == (((n + 1) / 2) % 3)))
        res = (res + MOD - 1) % MOD;
    return res;
}

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

    cin >> n >> q;
    cin >> s;

    dp[0][0] = 1;
    for (int w = 1; w <= n; ++w) {
        for (int k = 0; k < min(w+1, 3); ++k)
            dp[w][k] = (dp[w - 1][k] + dp[w - 1][(k + 2) % 3]) % MOD;
    }
    
    for (int i = 0; i < n; ++i)
        update(s[i], i, +1);

    cout << result() << '\n';
    for (int i = 0; i < q; ++i) {
        int k;
        char c;
        cin >> k >> c;
        update(s[k - 1], k - 1, -1);
        update(c, k - 1, +1);
        s[k - 1] = c;
        cout << result() << '\n';
    }
    return 0;
}