Great Thermion Collider

Professor Bajtsztajn discovered a new type of elementary particle, the thermion. If his experiments succeed, thermions may help build a power plant that solves the energy problems of Bajtocja.

Thermions come in three kinds, called red, green, and blue. These names have nothing to do with the real colors of the particles or the frequencies of light. The professor simply had markers in those colors on hand.

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

Blue thermions do not react with other thermions, but they are unstable. 72 hours after a blue thermion is produced, it turns randomly into either a red or a green thermion. Neither change takes in or gives off energy.

The professor is preparing a controlled experimental reaction. In his laboratory he has arranged n thermions in a row as a chain. In a few days he plans to take the chain to the Great Thermion Collider, which is being built under the capital. Until then, all blue thermions will have changed into red or green.

At the Collider, the professor wants to run a sequence of reactions that releases n-1 bytejoules and leaves only one thermion at the end. In each reaction, two adjacent thermions in the chain take part. The thermion produced sits between its left and right neighbors and can take part in further reactions.

The question is whether such a sequence of reactions can be carried out once all blue thermions have changed.

Your task is to count, modulo $10^9 + 7$, the number of ways the blue thermions can change so that the full sequence of reactions can be carried out.

In addition, the professor changes the chain in his laboratory. Each time, he replaces one thermion with another (possibly of the same color). Compute the answer after each such change as well.

The first line contains two integers n and q (1 ≤ n ≤ 200 000, 0 ≤ q ≤ 100 000), the number of thermions in the chain and the number of changes.

The second line contains a string of n letters C, Z, or N, describing the initial chain. These stand for red, green, and blue thermions. The k-th letter is the color of the k-th thermion from the left.

Each of the next q lines contains an integer k_i (1 ≤ k_i ≤ n) and a letter C, Z, or N. This means that in the i-th step, the professor replaced the k_i-th thermion from the left with a new thermion of the given color.

Print q + 1 lines. Line i + 1 contains the answer for the chain after i changes (0 ≤ i ≤ q).

Each answer is the number of ways the blue thermions in that chain could change so that the full sequence of reactions releasing n - 1 bytejoules can be carried out, taken modulo $10^9 + 7$.

The initial chain is NNCCZ. On the way to the Large Hadron Collider, the two blue thermions can change in 4 ways.

• CCCCZ. The full sequence is impossible here. For example, CCCCZ becomes ZCCZ, then ZZZ, then ZC. This releases only 3 bytejoules, and no further reaction is possible because only thermions of the same color react.
• CZCCZ. The full sequence is possible: CZCCZ, CZZZ, CCZ, ZZ, C, releasing 4 bytejoules.
• ZCCCZ. The full sequence is possible: ZCCCZ, ZCZZ, ZCC, ZZ, C, releasing 4 bytejoules.
• ZZCCZ. The full sequence is possible: ZZCCZ, ZZZZ, ZZC, CC, Z, releasing 4 bytejoules.

Three of the four options allow the full sequence, so the first answer is 3.

The final chain after all changes is ZZNCZ. The full sequence is possible in only one variant, when the blue thermion becomes red, so the last answer is 1.