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
import sys

p = 10**9 + 7


class TurboPascal:
    tab = []
    tabs = []

    def __init__(self, l):
        (t0, t1, t2) = (1, 0, 0)
        for r in range(l + 1):
            self.tab.append((t0, t1, t2))
            self.tabs.append(t0 + t1 + t2)
            (t0, t1, t2) = ((t2 + t0) % p, (t0 + t1) % p, (t1 + t2) % p)

    def calc(self, c, z, n):
        if c < z + n:
            d1 = (z + n - c) % 3
            d2 = (3 - d1) % 3
        else:
            d1 = (c - z - n) % 3
            d2 = d1
        return self.tabs[n] - self.tab[n][d2]


class State:
    cc = [0, 0]
    zz = [0, 0]

    def __init__(self, l, ss):
        self.s = list(ss)
        self.l = l
        for i in range(l):
            if self.s[i] == "C":
                self.cc[i % 2] += 1
            elif self.s[i] == "Z":
                self.zz[i % 2] += 1
        self.update()

    def update(self):
        self.c = self.cc[0] + self.cc[1]
        self.z = self.zz[0] + self.zz[1]
        self.n = self.l - self.c - self.z

    def compute(self, pascal):
        bad = 0
        if self.l == 1:
            return 2 if self.s[0] == "N" else 1
        if self.l % 2 == 1:
            if self.cc[0] == 0 and self.zz[1] == 0:
                bad += 1
            if self.zz[0] == 0 and self.cc[1] == 0:
                bad += 1
        return (pascal.calc(self.c, self.z, self.n) + p - bad) % p

    def modify(self, idx, ch):
        if self.s[idx] == ch:
            return
        if self.s[idx] == "Z":
            self.zz[idx % 2] -= 1
        if ch == "Z":
            self.zz[idx % 2] += 1
        if self.s[idx] == "C":
            self.cc[idx % 2] -= 1
        if ch == "C":
            self.cc[idx % 2] += 1
        self.s[idx] = ch
        self.update()


def main():
    lines = sys.stdin.read().splitlines()
    l, q, = map(int, lines[0].split())
    turbo = TurboPascal(l)
    state = State(l, lines[1])
    sys.stdout.write(str(state.compute(turbo))+"\n")
    for z in range(q):
        ss = lines[2+z].split()
        state.modify(int(ss[0]) - 1, ss[1])
        sys.stdout.write(str(state.compute(turbo))+"\n")


if __name__ == "__main__":
    main()