Professor Albert Bajtsztajn has discovered a new type of elementary particle called a "termion". If his experiments are successful, it may be possible to build a power plant that will solve the energy problems of Byteland.

These particles come in three types: symbolically named red, green, and blue. These names have nothing to do with the actual colors of the particles or the frequencies of light waves; Professor Bajtsztajn simply happened to have markers in those colors.

Red and green termions can react, but only with another particle of the same color. When two red termions collide, they form one green termion, and we obtain 1 bajtojoule of energy from this reaction. When two green termions collide, they form one red termion, and we also obtain 1 bajtojoule of energy.

Blue termions do not react with other termions, but they are unstable. 72 hours after a blue termion is produced, it randomly turns into either a red or a green termion, with neither of these changes consuming or generating energy.

The professor is preparing an experimental, controlled reaction. To this end, he has prepared a chain of $n$ termions in his laboratory, arranged in a row. In a few days, he intends to take this chain to the Great Termion Collider, which is currently being built under the capital. By that time, all blue termions will have turned into red or green ones.

In the Collider, the professor wants to perform a sequence of reactions that will generate $n-1$ bajtojoules of energy, leaving only one termion at the end. Two adjacent termions in the chain can participate in each reaction. The resulting termion is adjacent to the termions on the left and right and can participate in subsequent reactions with them.

The question is, what are the chances that when all blue termions have changed, such a sequence of reactions will be possible to perform?

Your task is to calculate the number of ways (modulo $10^9 + 7$) the blue termions can change so that a full sequence of reactions can be performed.

Additionally, the professor performs changes in the chain in his laboratory, replacing one termion with another (perhaps not changing its type) each time. Calculate the result after each such change as well.

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n \le 200\,000$, $0 \le q \le 100\,000$), representing the number of termions in the chain and the number of changes, respectively.

The second line of input describes the initial state of the termion chain. Its description is a string consisting of $n$ letters 'C', 'Z', or 'N', representing a red, green, or blue termion, respectively. The $k$-th letter of the string denotes the color of the $k$-th termion from the left.

The next $q$ lines describe subsequent changes in the chain. Each of these lines contains an integer $k_i$ ($1 \le k_i \le n$) and a letter 'C', 'Z', or 'N'. This means that in the $i$-th step, the professor replaced the $k_i$-th termion from the left with a new termion of the color described by the given letter.

Output

The output should contain $q + 1$ lines. Line $i + 1$ should contain a single integer – the result for the chain formed after $i$ changes ($0 \le i \le q$).

Each result is the remainder of the division by $10^9 + 7$ of the number of ways the blue termions in the resulting chain could change so that, in effect, it would be possible to perform a full sequence of reactions generating $n - 1$ bajtojoules of energy.

Examples

Input 1

5 3
NNCCZ
3 N
2 Z
1 Z

Output 1

3
5
3
1

Note

Explanation of the example: The initial chain is ‘NNCCZ’. On the journey to the Great Hadron Collider, the two blue termions can change in 4 ways:

• ‘CCCCZ’. In this situation, performing a full sequence of reactions is impossible. For example, we can try: ‘CCCCZ’ → ‘ZCCZ’ → ‘ZZZ’ → ‘ZC’. We only obtained 3, not 4, bajtojoules. It is impossible to perform another reaction because only termions of the same color react.
• ‘CZCCZ’. We can perform a full sequence of reactions: ‘CZCCZ’ → ‘CZZZ’ → ‘CCZ’ → ‘ZZ’ → ‘C’, obtaining 4 bajtojoules.
• ‘ZCCCZ’. We can perform a full sequence of reactions: ‘ZCCCZ’ → ‘ZCZZ’ → ‘ZCC’ → ‘ZZ’ → ‘C’, obtaining 4 bajtojoules.
• ‘ZZCCZ’. We can perform a full sequence of reactions: ‘ZZCCZ’ → ‘ZZZZ’ → ‘ZZC’ → ‘CC’ → ‘Z’, obtaining 4 bajtojoules.

In three out of four possibilities, we can perform a full sequence of reactions, so the correct answer in the first line is 3.

The final version of the chain after all termion changes is ‘ZZNCZ’. In this situation, a full sequence of reactions can be performed in only one variant: if the blue termion turns into a red one. For this reason, the correct answer in the last line is 1.