Problem Description

This problem is translated from PA 2022 Round 1 Wielki Zderzacz Termionów.

Professor Albert Bynstein has discovered a new elementary particle: the thermion. If his experiment succeeds, a power plant can be built with its help, which would solve Byteland's energy problem.

There are three types of these particles, represented as red, green, and blue. These names have nothing to do with the particles' actual colors or the wavelength of light; they are just labels Professor Bynstein marked on the particles using colored pens.

Red and green thermions can react, but only with another particle of the same color. When two red thermions collide, they produce one green thermion and release $1$ bytejoule of energy. If two green thermions collide, they produce one red thermion and also release $1$ bytejoule of energy.

Blue thermions do not react with other thermions, but they are unstable. After $72$ hours from the moment a blue thermion is created, it will randomly turn into either a red thermion or a green thermion. Turning into either thermion does not release any energy.

The professor is preparing a controlled experimental reaction. For this, he has prepared $n$ thermions lined up in a row in his laboratory. A few days later, he plans to take these thermions to the large thermion collider currently being built underground in the capital. By that time, all blue thermions will have turned into red or green thermions.

In the collision experiment, the professor wants to perform a sequence of reactions that produces $n-1$ bytejoules of energy and finally leaves only one thermion. In each reaction, he may choose two adjacent thermions. The newly produced thermion becomes adjacent to the thermions on its left and right, and it can undergo further reactions with them.

The question is: after all blue thermions have changed, what is the probability that there exists a feasible sequence of reactions.

Your task is to compute how many possible ways the blue thermions can change (modulo $10^9+7$) so that the full reaction sequence can be carried out.

In addition, the professor will also modify the positions of the thermions in his lab, each time replacing one thermion with another (possibly not changing its type). After each such change, you must also compute the result.

Input Format

The first line contains two integers $n$ and $q$, representing the number of thermions and the number of changes.

The second line contains a string of length $n$, describing the initial arrangement of thermions. The string contains only the characters C, Z, and N, representing red, green, and blue thermions, respectively. The $k$-th character from the left indicates the color of the $k$-th thermion.

The next $q$ lines describe modifications to the string above. Each line contains a number $k_i$ and a character (one of C, Z, N). This means that in step $i$, the professor replaces the $k_i$-th particle with the new particle represented by that character.

Output Format

Output $q+1$ lines. On line $i+1$, output one integer: the answer after the first $i$ modifications.

Output the number of ways the blue thermions can change (modulo $10^9+7$) such that the full reaction sequence can be carried out and produces $n-1$ bytejoules of energy.

5 3
NNCCZ
3 N
2 Z
1 Z

3
5
3
1

Hint

For $100\%$ of the testdata, the following constraints hold:

$1\le n\le 2 \times 10 ^ 5, 0\le q\le 10 ^ 5, 1\le k_i\le n$。

Translated by ChatGPT 5