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
import sys
input = sys.stdin.readline

n, q = map(int, input().split())

l = list(input().strip())

nc = 0
cc = 0
zc = 0
a1 = 0
a2 = 0
for i in range(n):
    c = l[i]
    if c == 'N':
        nc += 1
    elif c == 'C':
        cc += 1

        if i % 2:
            a1 += 1
        else:
            a2 += 1
    else:
        assert c == 'Z'
        zc += 1

        if i % 2:
            a2 += 1
        else:
            a1 += 1




MOD = 10 ** 9 + 7

dp = [[1], [0], [0]]
for i in range(200010):
    u = (dp[0][-1] + dp[-1][-1]) % MOD
    v = (dp[1][-1] + dp[0][-1]) % MOD
    w = (dp[2][-1] + dp[1][-1]) % MOD

    dp[0].append(u)
    dp[1].append(v)
    dp[2].append(w)

def cnt():
    good = 0
    for i in range(3):
        if ((cc + i) - (zc + nc - i)) % 3 != 0:
            good += dp[i][nc]

    if n % 2 == 1 and a1 == 0:
        good -= 1
    if n % 2 == 1 and a2 == 0:
        good -= 1

    return good % MOD

out = [cnt()]

for _ in range(q):
    i, c = input().split()
    i = int(i) - 1

    oc = l[i]
    if oc == 'N':
        nc -= 1
    elif oc == 'C':
        cc -= 1

        if i % 2:
            a1 -= 1
        else:
            a2 -= 1
    else:
        assert oc == 'Z'
        zc -= 1

        if i % 2:
            a2 -= 1
        else:
            a1 -= 1

    #Redo
    l[i] = c
    if c == 'N':
        nc += 1
    elif c == 'C':
        cc += 1

        if i % 2:
            a1 += 1
        else:
            a2 += 1
    else:
        assert c == 'Z'
        zc += 1

        if i % 2:
            a2 += 1
        else:
            a1 += 1

    out.append(cnt())

print('\n'.join(map(str, out)))