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
termions_combinations = {}
def get_all_combinates(termions:str):
    if 'N' not in termions:
        return [termions]
    
    if termions in termions_combinations.keys():
        return termions_combinations[termions]
    
    index = termions.find('N')

    sequence = termions[:index] + 'Z' + termions[index+1:]
    results1 = get_all_combinates(sequence)

    sequence = termions[:index] + 'C' + termions[index+1:]
    results2 = get_all_combinates(sequence)

    results = []
    for result in results1:
        results.append(result)
    
    for result in results2:
        results.append(result)

    termions_combinations[termions] = results

    return results

pieces_of_termions = {}
def termions_reaction(termions, expected_value, energy=0):
    if len(termions) == 1 or energy > expected_value+1:
        return energy
    
    if termions in pieces_of_termions.keys():
        energies = pieces_of_termions[termions]
        for e in energies:
            if e == expected_value:
                return e
        return e

    energy1 = 0
    energy2 = 0

    for i in range(0, len(termions)-1):
        piece = termions[i:i+2]
        if piece == 'ZZ':
            new_termions_combination = termions[:i] + 'C' + termions[i+2:]
            new_energy = energy+1
            
            energy1 = termions_reaction(new_termions_combination, expected_value, new_energy)
            pieces_of_termions[termions] = [energy1]
            if energy1 == expected_value:
                return energy1
        if piece == 'CC':
            new_termions_combination = termions[:i] + 'Z' + termions[i+2:]
            new_energy = energy+1
            energy2 = termions_reaction(new_termions_combination, expected_value, new_energy)

            if termions in pieces_of_termions.keys():
                pieces_of_termions[termions].append(energy2)
            else:
                pieces_of_termions[termions] = [energy2]

            if energy2 == expected_value:
                return energy2
        
    return energy


def calculate_correct_combinations(termions, n):
    combines = get_all_combinates(termions)
    correct_combines=0
    for combine in combines:
        energy = termions_reaction(combine, n-1)
        if energy == n-1:
            correct_combines += 1    
    return correct_combines
        

n, q = [int(i) for i in input().split()]
termions = input()

output = []
output.append(calculate_correct_combinations(termions, n))

for i in range(q):
    inp = input().split()
    idx, letter = [int(inp[0]), inp[1]]
    combination = termions[:idx-1] + letter + termions[idx:]
    output.append(calculate_correct_combinations(combination, n))
    termions = combination

for o in output:
    print(o)