bear-and-immugene

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^9+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^9+7 the number of different subsequences of the given Immugene after the i-th change.

Constraints
1 ≤ N ≤ 10^6
1 ≤ Q ≤ 10^5

SAMPLE INPUT
4 7
GTCG
2 G
3 A
2 C
3 G
3 G
4 T
1 T

SAMPLE OUTPUT
10
10
15
10
10
14
15

Explanation

First, the 2-nd letter is changed to G and the whole Immugene is GGCG.
There are 10 different subsequences: "", "C", "CG", "G", "GC", "GCG", "GG", "GGC", "GGCG", "GGG".

After the second change the Immugene is GGAG and the answer is the same.

After the third change the Immugene is GCAG and there are 15 different subsequences.

Source: hackerearth | Difficulty: HARD
Tags: Fundamentals


Solutions: