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$.
The first line contains two integers $n$ and $q$ ($1 <= n, q <= 200 thin 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 <= i <= 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).
Print $q + 1$ lines, each with the current answer modulo $1000000007$.
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_.
## Input
The first line contains two integers $n$ and $q$ ($1 <= n, q <= 200 thin 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 <= i <= 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$.
[samples]
## 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_.
**Definitions**
Let $ s \in \{ \text{A-Z}, ? \}^n $ be a pattern string of length $ n $.
Let $ \mathcal{C} = \{ \text{A}, \text{B}, \dots, \text{Z} \} $ be the set of uppercase English letters.
Let $ V = \{ \text{A}, \text{E}, \text{I}, \text{O}, \text{U} \} $ be the set of vowels.
Let $ S = \{ \text{S}, \text{D} \} $ be the sad-making letters.
Let $ H = \{ \text{H} \} $ be the happy-making letter.
Let $ N = \mathcal{C} \setminus (V \cup S \cup H) $ be the neutral letters.
Define the state transition function $ f: \{ \text{happy}, \text{sad} \} \times \mathcal{C} \to \{ \text{happy}, \text{sad} \} $:
- $ f(\text{happy}, c) = \begin{cases}
\text{sad} & \text{if } c \in S \cup V \\
\text{happy} & \text{if } c \in H \\
\text{happy} & \text{if } c \in N
\end{cases} $
- $ f(\text{sad}, c) = \begin{cases}
\text{sad} & \text{if } c \in S \\
\text{happy} & \text{if } c \in H \cup V \\
\text{sad} & \text{if } c \in N
\end{cases} $
Let $ x $ be the number of `?` in $ s $.
Each `?` can be replaced by any letter in $ \mathcal{C} $, yielding $ 26^x $ total assignments.
Let $ \text{dp}[i][b] $ be the number of ways to assign letters to the first $ i $ characters of $ s $ such that Limak’s mood after reading them is $ b \in \{0, 1\} $ (0 = happy, 1 = sad), starting from happy (state 0).
**Constraints**
1. $ 1 \le n, q \le 200000 $
2. Initial and updated $ s $ contains only valid characters: uppercase letters or `?`
3. Updates are persistent and modify one character at position $ i $ (1-indexed).
4. All computations modulo $ 10^9 + 7 $.
**Objective**
For the current pattern $ s $, compute the number of assignments to `?` such that the final mood is happy (state 0), i.e., $ \text{dp}[n][0] $.
For each character $ s_i $:
- If $ s_i \in \mathcal{C} $:
- Determine its effect $ \Delta_i \in \{ \text{happy}, \text{sad}, \text{flip}, \text{none} \} $ as per rules.
- If $ s_i = ? $:
- Let $ w_i = $ number of letters in $ \mathcal{C} $ that cause a transition from current state $ b $ to target state $ b' $.
- Specifically, for state $ b \in \{0,1\} $, define:
$$
\text{weight}(b) = \sum_{c \in \mathcal{C}} \mathbf{1}_{f(b, c) = b'}
$$
Precompute for each state:
- From happy (0):
- To happy: $ |H \cup N| = 1 + (26 - 5 - 2 - 1) = 1 + 18 = 19 $
- To sad: $ |S \cup V| = 2 + 5 = 7 $
- From sad (1):
- To happy: $ |H \cup V| = 1 + 5 = 6 $
- To sad: $ |S \cup N| = 2 + 18 = 20 $
Thus, for a `?`:
- If current state is happy (0), contributes 19 to next happy, 7 to next sad.
- If current state is sad (1), contributes 6 to next happy, 20 to next sad.
For fixed letters, use deterministic transition.
**Dynamic Programming Recurrence**
Initialize:
$ \text{dp}[0][0] = 1 $, $ \text{dp}[0][1] = 0 $
For each position $ i = 1 $ to $ n $:
- If $ s_i \in \mathcal{C} $:
- Compute transition $ t = f(\cdot, s_i) $:
- If $ s_i \in S $: $ \text{dp}[i][1] += \text{dp}[i-1][0] + \text{dp}[i-1][1] $
- If $ s_i \in H $: $ \text{dp}[i][0] += \text{dp}[i-1][0] + \text{dp}[i-1][1] $
- If $ s_i \in V $: $ \text{dp}[i][1 - b] += \text{dp}[i-1][b] $ for $ b \in \{0,1\} $
- If $ s_i \in N $: $ \text{dp}[i][b] += \text{dp}[i-1][b] $ for $ b \in \{0,1\} $
- If $ s_i = ? $:
- $ \text{dp}[i][0] = \text{dp}[i-1][0] \cdot 19 + \text{dp}[i-1][1] \cdot 6 $
- $ \text{dp}[i][1] = \text{dp}[i-1][0] \cdot 7 + \text{dp}[i-1][1] \cdot 20 $
**Output**
After initial string and each update, output $ \text{dp}[n][0] \mod 1000000007 $.