Thermal Ion Collision

Professor Bynstein has discovered a new fundamental particle called a thermal ion. There are three types of these particles – red, green and blue. Although the colors are only labels, the red and green ions can react under very particular conditions:

• When two red thermal ions collide, they react producing a green ion and release $1$ unit of energy.
• When two green thermal ions collide, they react producing a red ion and release $1$ unit of energy.
• Blue thermal ions do not react with any ion; however, after 72 hours each blue ion independently transforms into either a red ion or a green ion (with no energy released).

Professor Bynstein has arranged n thermal ions in a row in his laboratory. By the time the ions are brought to the large underground collider in the capital, all the blue ions will have already changed into either red or green. In the collider, a series of reactions is planned where in each reaction two adjacent ions react (note that only ions of the same color may react). The reaction replaces the two ions by a single ion (whose color is determined by the reaction rule) that remains adjacent to its neighbours. The goal is to perform exactly n − 1 reactions (thereby releasing n − 1 energy units) and end up with exactly one ion.

Your task is to determine, modulo $10^9+7$, in how many ways the blue ions can change (i.e. which ones become red and which green) so that there exists at least one valid reaction sequence which reduces the row of ions to a single ion. Furthermore, the experiment is dynamic. After the initial configuration, the professor makes several changes – in each change a single ion is replaced by another (possibly of the same type) and you must again compute the required number for the new configuration.

Reaction details:

• If two adjacent ions of type X (where X is red or green) react, the resulting ion will be the opposite color (i.e. red becomes green, and green becomes red).
• The transformation of a blue ion does not produce energy and is independent.

Note on validity: A configuration (with blue ions replaced by red or green) is called fully reducible if there exists a sequence of reactions (choosing adjacent equal colored ions at every step) that reduces the entire row to a single ion.

inputFormat

The first line contains two integers n and q — the number of ions and the number of updates, respectively.

The second line contains a string of length n consisting only of the characters 'R', 'G' and 'B', representing the initial types of the ions (red, green, blue respectively).

Each of the following q lines contains an integer i (1-indexed) and a character c (one of 'R', 'G', 'B'), indicating that the ion at position i is changed to type c. After each update, consider the new configuration.

outputFormat

For the initial configuration and after each update, output the number of ways (modulo $10^9+7$) the blue ions may change (each independently to 'R' or 'G') so that the entire configuration is fully reducible. That is, there exists at least one sequence of adjacent reactions that reduces the row of ions to a single ion.

Print each answer on a separate line.

sample

3 2
RBG
2 R
3 B

2
1
1