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
#include <stdio.h>

#define M 1000000007
#define INV3 ((M + 1) / 3)

char buf[200001];
int nums[200000];

int the_sum = 0;
int the_even_cnt = 0;
int the_odd_cnt  = 0;
int the_zero_cnt = 0;

int val(char c) {
	switch (c) {
		case 'C': return -1;
		case 'Z': return +1;
	}
	return 0;
}

/* (-1)^x */
int alt(int x)
{
	return 1 - ((x & 1) << 1);
}

void update(int x, int v)
{
	// step 1: set to zero
	the_sum -= nums[x];
	if (alt(x) * nums[x] > 0)
		the_even_cnt--;
	if (alt(x) * nums[x] < 0)
		the_odd_cnt--;
	if (nums[x] != 0)
		the_zero_cnt++;

	// step 2: set to v
	the_sum += v;
	if (alt(x) * v > 0)
		the_even_cnt++;
	if (alt(x) * v < 0)
		the_odd_cnt++;
	if (v != 0)
		the_zero_cnt--;

	nums[x] = v;
}

int p2[200001];

void calc_p2(int n)
{
	p2[0] = 1;
	for (int i = 0; i < n; i++) {
		p2[i+1] = p2[i] * 2;
		if (p2[i+1] > M)
			p2[i+1] -= M;
	}
}

/* C(k, x) + C(k, x+3) + ... */
int s3(int k, int x)
{
	int a[3][6] = {
		{  2,  1, -1, -2, -1,  1 },
		{ -1,  1,  2,  1, -1, -2 },
		{ -1, -2, -1,  1,  2,  1 },
	};

	return ((long long)INV3 * (p2[k] + a[x][k%6])) % M;
}

int answer(int n)
{
	int k = the_zero_cnt;
	int x = (2 * (the_zero_cnt - the_sum)) % 3;
	int bad = 0;
	int good;

	if (x < 0)
		x += 3;

	bad = s3(k, x);

	if ((n & 1) && n > 1) {
		if (the_even_cnt == 0)
			bad++;
		if (the_odd_cnt == 0)
			bad++;
	}

	if (bad >= M)
		bad -= M;
	good = p2[k] - bad;
	if (good < 0)
		good += M;

	return good;
}

int main(void)
{
	int n, q;

	scanf("%d %d", &n, &q);
	scanf("%s", buf);

	the_zero_cnt = n;
	for (int i = 0; i < n; i++)
		update(i, val(buf[i]));

	calc_p2(n);

	printf("%d\n", answer(n));
	for (int i = 0; i < q; i++) {
		int x;
		char c;
		scanf("%d %c", &x, &c);
		update(x-1, val(c));
		printf("%d\n", answer(n));
	}

	return 0;
}