Limak is an old brown bear. He is a famous biotechnology scientist. He specializes at examining bear DNA. Years ago he started a research on one particular gene, responsible for immunity to diseases. Limak called it Immugene.

Immugene can be represented as a string of the length N made of four possible letters A, C, T, G. The string is 1-indexed (letters are numbered 1 through N).

Limak suspects that each of the 2^N subsequences protects from one type of diseases. Not necessarily all 2^N subsequences are different though. Different subsequences help to avoid different types of diseases. But unfortunately, equal subsequences protect from the same type of diseases.

Limak claims that one's immunity is related to the number of different subsequences in Immugene. This thesis is hard to check because Immugene tends to change.

John is a bear too, and a friend of Limak. Some time ago Limak started to study John's health condition and his Immugene. Limak remembers John's initial Immugene. Also, during the observation Limak noted Q changes of single letters. After each change Limak wants to compare John's health and Immugene.

Limak isn't good at programming though. You must help him with his research. After each of Q changes print modulo 10⁹+7 the number of different subsequences.

Input format

The fist line contains two integers N and Q, representing the length of the examined Immugene and the number of changes.

The second line contains a string of the length N, representing the initial Immugene.

The next Q lines describe changes. Each line contains an integer x and a letter y. x represents an index (between 1 and N, inclusive). y is one of letters A, C, T, G. The x-th letter is changing to y at this moment.

Output format

You should print Q lines in total.

In the i-th line print modulo 10⁹+7 the number of different subsequences of the given Immugene after the i-th change.

Constraints

1 ≤ N ≤ 10⁶
1 ≤ Q ≤ 10⁵

Subtasks

Extra constraints	Points	Tests
N, Q ≤ 15	10	1-1
N, Q ≤ 2000	40	2-5
no extra constraints	50	6-10