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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <array>
#include <iostream>
#include <vector>

#ifdef PERR
#include "perr.h"
#else
static struct Perr {template <typename T> constexpr Perr& operator<<(T const &any) {return *this;}} perr;
#endif

using arr3_t = std::array< int, 3 >;
using cache_t = std::vector< arr3_t >;

const int PRIME = 1e9 + 7;
const int RED = 0;
const int GREEN = 2;
const int BLUE = 4;
const int EVEN = 0;
const int ODD = 1;

struct Stats {
	int data[6] = {0, 0, 0, 0, 0, 0};

	static int color2index(char color) {
		if(color == 'C') return RED;
		if(color == 'Z') return GREEN;
		return BLUE;
	}

	void incr(char color, int rem, int delta = 1) {
		data[color2index(color) + rem] += delta;
	}

	void decr(char color, int rem) {
		incr(color, rem, -1);
	}

	int red()   const { return data[RED]   + data[RED   + ODD]; }
	int green() const { return data[GREEN] + data[GREEN + ODD]; }
	int blue()  const { return data[BLUE]  + data[BLUE  + ODD]; }
	int all()   const { return red() + green() + blue(); }
	
	int green_even() const { return data[GREEN + EVEN]; }
	int green_odd()  const { return data[GREEN + ODD ]; }
	int red_even()   const { return data[RED   + EVEN]; }
	int red_odd()    const { return data[RED   + ODD ]; }

	bool has_red_green_triplet() const { return (2 * red() + green()) % 3 == 0; }
	bool did_block() const {
		if (all() == 1) return false;
		if (red_even() + green_odd() == 0) return true;
		if (red_odd() + green_even() == 0) return true;
		return false;
	}

	int red_block() const {
		if( all() == 1 )    return 0;
		if( all() % 2 == 0) return 0;

		if( 0 < green_even() ) return 0;
		if( 0 < red_odd()    ) return 0;

		return 1;
	}

	int green_block() const {
		if( all() == 1 )    return 0;
		if( all() % 2 == 0) return 0;

		if( 0 < red_even()  ) return 0;
		if( 0 < green_odd() ) return 0;

		return 1;
	}
};

struct Cache { /* get rid of the reds, one red = two greens */
	cache_t c3 = { {0, 1, 1} };

	void grow() {
		c3.push_back({0, 0, 0});

		size_t sz = c3.size();
		arr3_t& prev = c3[sz - 2];
		arr3_t& next = c3[sz - 1];

		for(int i = 0; i < 3; ++i) {
			int ni1 = (i + 1) % 3;
			next[ni1] += prev[i];
			next[ni1] %= PRIME;

			int ni2 = (i + 2) % 3;
			next[ni2] += prev[i];
			next[ni2] %= PRIME;
		}
	};

	int get(int red, int green, int blue) {
		while(c3.size() < blue + 1) {
			grow();
		}

		int col = ((2 * red + green) % 3);
		return c3[blue][col];
	}
};


std::ostream& operator<< (std::ostream& os, Stats const& stats) {
	os << "\n";
	os << "RED   C " << stats.data[0] << " " << stats.data[1] << "\n";
	os << "GREEN Z " << stats.data[2] << " " << stats.data[3] << "\n";
	os << "BLUE  N " << stats.data[4] << " " << stats.data[5] << "\n";
	return os;
}

int solve(Stats const& stats, Cache& cache) {
	if(stats.blue() == 0) {
		if(stats.has_red_green_triplet()) return 0;
		if(stats.did_block()) return 0;
		return 1;
	}

	int res = cache.get(stats.red(), stats.green(), stats.blue());
	res -= stats.red_block();
	res -= stats.green_block();
	return res;
}

int main() {
	int len; std::cin >> len;
	int num_mut; std::cin >> num_mut;
	Stats stats;
	Cache cache;

	std::string chain;
	for (int i = 0; i < len; ++i) {
		char color; std::cin >> color;
		chain.push_back(color);
		stats.incr(color, i % 2);
	}

	std::vector< int > result;
	result.reserve(num_mut + 1);

	result.push_back(solve(stats, cache));

	for(int i = 0; i < num_mut; ++i) {
		int pos = 0;    std::cin >> pos; pos -= 1;
		char new_color; std::cin >> new_color;

		int rem = pos % 2;

		char old_color = chain[pos];
		stats.decr(old_color, rem);
		stats.incr(new_color, rem);
		chain[pos] = new_color;

		result.push_back(solve(stats, cache));
	}

	for (int i = 0; i < result.size(); ++i) {
		std::cout << result[i] << "\n";
	}

	return 0;
}