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 #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; }