Matrix Exponentiation |
---|
Finished |
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 \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).
Print $$$q+1$$$ lines, each with the current answer modulo $$$1000000007$$$.
2 5 A? 2 O 1 H 1 ? 2 ? 2 H
6 1 0 7 403 26
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.
Name |
---|