{"problem":{"name":"H. String Mood Updates","description":{"content":"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_) fl","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10264H"},"statements":[{"statement_type":"Markdown","content":"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.\n\nLet a _valid_ character denote a question mark _?_ or an uppercase English letter _A-Z_.\n\nYou 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).\n\nAdditionally, 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$.\n\nThe first line contains two integers $n$ and $q$ ($1 <= n, q <= 200 thin 000$) — the length of the pattern and the number of updates.\n\nThe second line contains the initial pattern $s$ with $n$ valid characters.\n\nEach 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.\n\nCharacters in $s$ are $1$-indexed. After you change a character, this change stays on (updates are not temporary).\n\nPrint $q + 1$ lines, each with the current answer modulo $1000000007$.\n\nThe pattern-string $s$ is initially _A?_ and then after every next update: _AO_, _HO_, _?O_, _??_, _?H_.\n\nFor 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_.\n\n## Input\n\nThe 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).\n\n## Output\n\nPrint $q + 1$ lines, each with the current answer modulo $1000000007$.\n\n[samples]\n\n## Note\n\nThe 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_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\{ \\text{A-Z}, ? \\}^n $ be a pattern string of length $ n $.  \nLet $ \\mathcal{C} = \\{ \\text{A}, \\text{B}, \\dots, \\text{Z} \\} $ be the set of uppercase English letters.  \nLet $ V = \\{ \\text{A}, \\text{E}, \\text{I}, \\text{O}, \\text{U} \\} $ be the set of vowels.  \nLet $ S = \\{ \\text{S}, \\text{D} \\} $ be the sad-making letters.  \nLet $ H = \\{ \\text{H} \\} $ be the happy-making letter.  \nLet $ N = \\mathcal{C} \\setminus (V \\cup S \\cup H) $ be the neutral letters.  \n\nDefine the state transition function $ f: \\{ \\text{happy}, \\text{sad} \\} \\times \\mathcal{C} \\to \\{ \\text{happy}, \\text{sad} \\} $:  \n- $ f(\\text{happy}, c) = \\begin{cases} \n\\text{sad} & \\text{if } c \\in S \\cup V \\\\\n\\text{happy} & \\text{if } c \\in H \\\\\n\\text{happy} & \\text{if } c \\in N \n\\end{cases} $  \n- $ f(\\text{sad}, c) = \\begin{cases} \n\\text{sad} & \\text{if } c \\in S \\\\\n\\text{happy} & \\text{if } c \\in H \\cup V \\\\\n\\text{sad} & \\text{if } c \\in N \n\\end{cases} $\n\nLet $ x $ be the number of `?` in $ s $.  \nEach `?` can be replaced by any letter in $ \\mathcal{C} $, yielding $ 26^x $ total assignments.\n\nLet $ \\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).\n\n**Constraints**  \n1. $ 1 \\le n, q \\le 200000 $  \n2. Initial and updated $ s $ contains only valid characters: uppercase letters or `?`  \n3. Updates are persistent and modify one character at position $ i $ (1-indexed).  \n4. All computations modulo $ 10^9 + 7 $.\n\n**Objective**  \nFor 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] $.\n\nFor each character $ s_i $:  \n- If $ s_i \\in \\mathcal{C} $:  \n  - Determine its effect $ \\Delta_i \\in \\{ \\text{happy}, \\text{sad}, \\text{flip}, \\text{none} \\} $ as per rules.  \n- If $ s_i = ? $:  \n  - Let $ w_i = $ number of letters in $ \\mathcal{C} $ that cause a transition from current state $ b $ to target state $ b' $.  \n  - Specifically, for state $ b \\in \\{0,1\\} $, define:  \n    $$\n    \\text{weight}(b) = \\sum_{c \\in \\mathcal{C}} \\mathbf{1}_{f(b, c) = b'}\n    $$  \n    Precompute for each state:  \n    - From happy (0):  \n      - To happy: $ |H \\cup N| = 1 + (26 - 5 - 2 - 1) = 1 + 18 = 19 $  \n      - To sad: $ |S \\cup V| = 2 + 5 = 7 $  \n    - From sad (1):  \n      - To happy: $ |H \\cup V| = 1 + 5 = 6 $  \n      - To sad: $ |S \\cup N| = 2 + 18 = 20 $  \n\nThus, for a `?`:  \n- If current state is happy (0), contributes 19 to next happy, 7 to next sad.  \n- If current state is sad (1), contributes 6 to next happy, 20 to next sad.  \n\nFor fixed letters, use deterministic transition.\n\n**Dynamic Programming Recurrence**  \nInitialize:  \n$ \\text{dp}[0][0] = 1 $, $ \\text{dp}[0][1] = 0 $\n\nFor each position $ i = 1 $ to $ n $:  \n- If $ s_i \\in \\mathcal{C} $:  \n  - Compute transition $ t = f(\\cdot, s_i) $:  \n    - If $ s_i \\in S $: $ \\text{dp}[i][1] += \\text{dp}[i-1][0] + \\text{dp}[i-1][1] $  \n    - If $ s_i \\in H $: $ \\text{dp}[i][0] += \\text{dp}[i-1][0] + \\text{dp}[i-1][1] $  \n    - If $ s_i \\in V $: $ \\text{dp}[i][1 - b] += \\text{dp}[i-1][b] $ for $ b \\in \\{0,1\\} $  \n    - If $ s_i \\in N $: $ \\text{dp}[i][b] += \\text{dp}[i-1][b] $ for $ b \\in \\{0,1\\} $  \n- If $ s_i = ? $:  \n  - $ \\text{dp}[i][0] = \\text{dp}[i-1][0] \\cdot 19 + \\text{dp}[i-1][1] \\cdot 6 $  \n  - $ \\text{dp}[i][1] = \\text{dp}[i-1][0] \\cdot 7 + \\text{dp}[i-1][1] \\cdot 20 $\n\n**Output**  \nAfter initial string and each update, output $ \\text{dp}[n][0] \\mod 1000000007 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10264H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}