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
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <string>
#include <vector>

struct Change
{
	long index{};
	char letter{};
};

long long getNewtonSymbol(long long n, long long k) {
	const long long divider = 1000000007;
	long long result = 1;
	for (long long i = 1; i <= k; i++) {
		result *= (n - i + 1);
		result /= i;
	}
	return result % divider;
}

struct Particles
{
	std::string p;
	long long countC{};
	long long countZ{};
	long long countN{};

	void countLetters() {
		countC = 0;
		countZ = 0;
		countN = 0;
		for (auto letter : p) {
			if (letter == 'C') {
				countC++;
			} else if (letter == 'Z') {
				countZ++;
			} else if (letter == 'N') {
				countN++;
			}
		}
	}

	void update(const Change &c) {
		if (p[c.index] == 'C') {
			countC--;
		} else if (p[c.index] == 'Z') {
			countZ--;
		} else if (p[c.index] == 'N') {
			countN--;
		}
		p[c.index] = c.letter;
		if (c.letter == 'C') {
			countC++;
		} else if (c.letter == 'Z') {
			countZ++;
		} else if (c.letter == 'N') {
			countN++;
		}
	}

	long long getNumberOfCombinations() {
		const long long divider = 1000000007;
		long long combinationsCount{};

		for (long long numberOfC = 0; numberOfC <= countN; numberOfC++) {
			long long numberOfZ = countN - numberOfC;
			long long allC = numberOfC + countC;
			long long allZ = numberOfZ + countZ;

			long long currentModulo = getCurrentModulo3(allC, allZ);
			if (currentModulo != 0) {

				combinationsCount += getNewtonSymbol(countN, numberOfC);
				combinationsCount %= divider;	
			}
		}		

		return combinationsCount;	
	}
	long long getCurrentModulo3(long long x, long long y) {
		if (x == y) {
			return 0;
		}
		long long higher = std::max(x, y);
		long long lower = std::min(x, y);
		return (higher - lower) % 3;
	}

};

int main() {
	long letterCount{};
	long changesCount{};
	Particles particles;
	std::cin >> letterCount;
	std::cin >> changesCount;
	std::cin >> particles.p;

	particles.countLetters();

	std::vector<Change> changes;
	for (long i = 0; i < changesCount; i++) {
		long position{};
		char letter{};
		Change change;
		std::cin >> position;
		std::cin >> letter;
		change.index = position - 1;
		change.letter = letter;
		changes.push_back(change);
	}
	std::cout << particles.getNumberOfCombinations() << std::endl;

	for (long i = 0; i < changes.size(); i++) {
		particles.update(changes[i]);
		std::cout << particles.getNumberOfCombinations() << std::endl;
	}

	return 0;
}