H. String Mood Updates
time limit per test
2.0 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Limak can be either happy or sad. His mood changes (or stays same) when he reads an English uppercase letter. Letters S and D always make him sad, H makes him happy, and every vowel (AEIOU) flips his mood. Other letters do nothing. Limak is happy right now and he wants to be happy after reading a string.

Let a valid character denote a question mark ? or an uppercase English letter A-Z.

You are given a pattern-string $$$s$$$ with $$$n$$$ valid characters. If there are, say, $$$x$$$ question marks, there are $$$26^x$$$ ways to replace them with uppercase letters A-Z. Your task is to count ways of replacing so that Limak would be happy after reading a new string (if he's happy before).

Additionally, there are $$$q$$$ updates of form ,,$$$i \ c$$$", each modifying one character of the pattern $$$s$$$. You need to print the answer before updates and after every update, modulo $$$10^9+7$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$) — the length of the pattern and the number of updates.

The second line contains the initial pattern $$$s$$$ with $$$n$$$ valid characters.

Each of the following $$$q$$$ lines contains an integer $$$i$$$ ($$$1 \leq i \leq n$$$) and a valid character $$$c$$$. The update changes the $$$i$$$-th character of $$$s$$$ to $$$c$$$. No update tries to change a character into the same character.

Characters in $$$s$$$ are $$$1$$$-indexed. After you change a character, this change stays on (updates are not temporary).

Output

Print $$$q+1$$$ lines, each with the current answer modulo $$$1000000007$$$.

Example
Input
2 5
A?
2 O
1 H
1 ?
2 ?
2 H
Output
6
1
0
7
403
26
Note

The pattern-string $$$s$$$ is initially A? and then after every next update: AO, HO, ?O, ??, ?H.

For the initial pattern A?, there are six good ways to replace all question marks: AA, AE, AH, AI, AO, AU. The first letter is a vowel so it flips Limak's mood from happy to sad. The second letter must be a vowel or H.