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

M = 1000000007

class ParPosTracker(object):
    def __init__(self):
        self.c_o = self.c_e = self.z_o = self.z_e = 0

    def possible_czczcz(self):
        res = 0
        if self.c_e == 0 and self.z_o == 0:
            res += 1
        if self.c_o == 0 and self.z_e == 0:
            res += 1
        return res

    def update(self, sym, pos, change):
        parity = pos % 2
        if sym == 90:
            if parity == 0:
                self.z_e += change
            else:
                self.z_o += change
        elif sym == 67:
            if parity == 0:
                self.c_e += change
            else:
                self.c_o += change

class Solver(object):
    def __init__(self):
        self.Q = self.calc_Q()
        self.n = self.z = self.c = 0
        self.par_pos_tracker = ParPosTracker()
        self.word = None
        self.swap_cnt = 0
        self.flen = 0

    def solve(self):
        self.load_initial()
        self.output_answer()
        for _ in range(self.swap_cnt):
            pos, sym = sys.stdin.readline().strip().split()
            sym = ord(sym)
            pos = int(pos)
            self.swap(pos, sym)
            self.output_answer()

    def load_initial(self):
        self.flen, self.swap_cnt = (int(v) for v in sys.stdin.readline().strip().split())
        self.word = bytearray(sys.stdin.readline().strip(), 'ascii')
        for i, b in enumerate(self.word):
            if b == 90: # Z
                self.z += 1
            elif b == 67: # C
                self.c += 1
            elif b == 78: # N
                self.n += 1
            self.par_pos_tracker.update(b, i + 1, 1)

    def swap(self, pos, sym):
        cur = self.word[pos-1]

        if cur == 90: # Z
            self.z -= 1
        elif cur == 67: # C
            self.c -= 1
        elif cur == 78: # N
            self.n -= 1

        if sym == 90: # Z
            self.z += 1
        elif sym == 67: # C
            self.c += 1
        elif sym == 78: # N
            self.n += 1
        
        self.par_pos_tracker.update(cur, pos, -1)
        self.par_pos_tracker.update(sym, pos, 1)
        self.word[pos-1] = sym

    def output_answer(self):
        c, z, n = self.c, self.z, self.n
        ec = c + n
        ez = z

        ans = 0
        for i in range(min(n+1, 3)):
            if self.check_sym_cnts(ec - i, ez + i):
                ans = (ans + self.Q[n * 3 + i]) % M

        if self.flen > 1 and self.flen % 2 == 1:
            ans = (ans + M - self.par_pos_tracker.possible_czczcz()) % M

        print(ans)

    def check_sym_cnts(self, c, z):
        return abs(c - z) % 3 != 0

    def calc_Q(self):
        q = [0] * (200001 * 3)
        q[0] = 1
        for i in range(1, 200001):
            for j in range(3):
                q[i * 3 + j] = (q[(i-1)*3 + (j + 3 - 1) % 3] + q[(i-1)*3 + j]) % M
                
        return q


Solver().solve()