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
#include <iostream>
  #include <stdio.h>
  #include <cstdio>
  using namespace std;


  int DIVISOR = 1000 * 1000 * 1000 + 7;
  const int MAX_LENGTH = 200 * 1000;
  int RED = 1;
  int GREEN = -1;
  int BLUE = 0;

  int sequenceLength;
  int nCorrections;
  int colorToValue[256];
  int sequence[MAX_LENGTH + 1];

  int abs(int value) {
    return (value < 0) ? -value : value;
  }

  bool isDivisibleBy3(int value) {
    return value % 3 == 0;
  }

  int signAt(int position) {
    return (position % 2) * 2 - 1;
  }

  int pascal[MAX_LENGTH + 1][3];

  void populatePascal() {
    pascal[0][0] = 1;
    pascal[0][1] = 0;
    pascal[0][2] = 0;
    for (int i = 1; i <= MAX_LENGTH; i++) {
      for (int j = 0; j < 3; j++) {
        pascal[i][j] = (pascal[i - 1][j] + pascal[i - 1][(j + 2) % 3]) % DIVISOR;
      }
    }
  }

  int main() {
    populatePascal();

    cin >> sequenceLength;
    cin >> nCorrections;

    colorToValue['C'] = RED;
    colorToValue['Z'] = GREEN;
    colorToValue['N'] = BLUE;

    getchar();
    for (int i = 1; i <= sequenceLength; i++) {
      char c = getchar();
      sequence[i] = colorToValue[c];
    }

    int triplity = 0;
    int stripity = 0;
    int blueity = 0;
    for (int i = 1; i <= sequenceLength; i++) {
      int color = sequence[i];
      triplity += color;
      stripity += color * signAt(i);
      blueity += 1 - color * color;
    }

    for (int iCorrection = 0; iCorrection <= nCorrections; iCorrection++) {
      if (iCorrection > 0) {
        int position;
        cin >> position;
        getchar();
        int newColor = colorToValue[getchar()];
        int oldColor = sequence[position];
        triplity -= oldColor;
        stripity -= oldColor * signAt(position);
        blueity -= 1 - oldColor * oldColor;
        triplity += newColor;
        stripity += newColor * signAt(position);
        blueity += 1 - newColor * newColor;
        sequence[position] = newColor;
      }

      int score = 0;
      for (int reding = 0; reding < 3; reding++) {
        int greening = blueity - reding;
        int finalTriplity = triplity + reding * RED + greening * GREEN;

        if (!isDivisibleBy3(finalTriplity)) {
          score += pascal[blueity][reding];
        }
      }

      if (sequenceLength % 2 == 1 && sequenceLength > 1) {
        if (abs(stripity) + blueity == sequenceLength) {
          // subtract 1 if stripes possible
          score--;
          if (blueity == sequenceLength) {
            // only blue termions, stripes possible in two ways
            score--;
          }
        }
      }
      printf("%d\n", score % DIVISOR);
    }

    return 0;
  }