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
#include <cstdio>
#define M 1000000007

int B[200001][2];

int r=0, g=0, b=0, p=0, q=0;
void a(char c, int i, int d)
{
  if (c=='C') r+=d, (i%2? p: q)+=d;
  else
  if (c=='Z') g+=d, (i%2? q: p)+=d;
  else
  b+=d;
}

void s()
{
  int t;
  t =B[b][1];
  t+=B[b][(r-g)%3==0],    t%=M;
  if (r+g+b>1 && (r+g+b)%2)
  t+=M-(p==r+g)-(q==r+g), t%=M;
  printf("%i\n", t);
}

int main()
{
  int n, q;
  scanf("%i%i ", &n, &q);
  char c, t[n];
  B[0][0]=1, B[0][1]=0;
  for (int i=0; i<n; i++)
  {
    B[i+1][0]=2*B[i][1]%M, B[i+1][1]=(B[i][0]+B[i][1])%M;
    c=getchar();
    a(c,i,1);
    t[i]=c;
  }
  s();
  for (int i=0; i<q; i++)
  {
    int k;
    scanf("%i %c", &k, &c);
    k--;
    a(t[k],k,-1);
    a(c,k,1);
    t[k]=c;
    s();
  }
  return 0;
}