{"problem":{"name":"G. Replace All","description":{"content":"Igor the analyst is at work. He learned about a feature in his text editor called \"Replace All\". Igor is too bored at work and thus he came up with the following problem: Given two strings _x_ and _y","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF794G"},"statements":[{"statement_type":"Markdown","content":"Igor the analyst is at work. He learned about a feature in his text editor called \"Replace All\". Igor is too bored at work and thus he came up with the following problem:\n\nGiven two strings _x_ and _y_ which consist of the English letters '_A_' and '_B_' only, a pair of strings (_s_, _t_) is called good if:\n\n*   _s_ and _t_ consist of the characters '_0_' and '_1_' only.\n*   1 ≤ |_s_|, |_t_| ≤ _n_, where |_z_| denotes the length of string _z_, and _n_ is a fixed positive integer.\n*   If we replace all occurrences of '_A_' in _x_ and _y_ with the string _s_, and replace all occurrences of '_B_' in _x_ and _y_ with the string _t_, then the two obtained from _x_ and _y_ strings are equal.\n\nFor example, if _x_ = _AAB_, _y_ = _BB_ and _n_ = 4, then (_01_, _0101_) is one of good pairs of strings, because both obtained after replacing strings are \"_01010101_\".\n\nThe flexibility of a pair of strings _x_ and _y_ is the number of pairs of good strings (_s_, _t_). The pairs are ordered, for example the pairs (_0_, _1_) and (_1_, _0_) are different.\n\nYou're given two strings _c_ and _d_. They consist of characters '_A_', '_B_' and '_?_' only. Find the sum of flexibilities of all possible pairs of strings (_c_', _d_') such that _c_' and _d_' can be obtained from _c_ and _d_ respectively by replacing the question marks with either '_A_' or '_B_', modulo 109 + 7.\n\n## Input\n\nThe first line contains the string _c_ (1 ≤ |_c_| ≤ 3·105).\n\nThe second line contains the string _d_ (1 ≤ |_d_| ≤ 3·105).\n\nThe last line contains a single integer _n_ (1 ≤ _n_ ≤ 3·105).\n\n## Output\n\nOutput a single integer: the answer to the problem, modulo 109 + 7.\n\n[samples]\n\n## Note\n\nFor the first sample, there are four possible pairs of (_c_', _d_').\n\nIf (_c_', _d_') = (_AA_, _A_), then the flexibility is 0.\n\nIf (_c_', _d_') = (_AB_, _A_), then the flexibility is 0.\n\nIf (_c_', _d_') = (_AA_, _B_), then the flexibility is 2, as the pairs of binary strings (_1_, _11_), (_0_, _00_) are the only good pairs.\n\nIf (_c_', _d_') = (_AB_, _B_), then the flexibility is 0.\n\nThus, the total flexibility is 2.\n\nFor the second sample, there are 21 + 22 + ... + 210 = 2046 possible binary strings of length not greater 10, and the set of pairs of good strings is precisely the set of pairs (_s_, _s_), where _s_ is a binary string of length not greater than 10.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Igor the analyst is at work. He learned about a feature in his text editor called \"Replace All\". Igor is too bored at work and thus he came up with the following problem:\n\nGiven two strings $x$ and $y$ which consist of the English letters $A$ and $B$ only, a pair of strings $(s, t)$ is called $\\text{good}$ if:\n\nFor example, if $x = AAB$, $y = BB$ and $n = 4$, then $(01, 0101)$ is one of good pairs of strings, because both obtained after replacing strings are \"01010101\".\n\nThe $\\text{flexibility}$ of a pair of strings $x$ and $y$ is the number of pairs of good strings $(s, t)$. The pairs are ordered, for example the pairs $(0, 1)$ and $(1, 0)$ are different.\n\nYou're given two strings $c$ and $d$. They consist of characters $A$, $B$ and $?$ only. Find the sum of flexibilities of all possible pairs of strings $(c', d')$ such that $c'$ and $d'$ can be obtained from $c$ and $d$ respectively by replacing the question marks with either $A$ or $B$, modulo $10^9 + 7$.\n\nThe first line contains the string $c$ ($1 ≤ |c| ≤ 3·10^5$).\n\nThe second line contains the string $d$ ($1 ≤ |d| ≤ 3·10^5$).\n\nThe last line contains a single integer $n$ ($1 ≤ n ≤ 3·10^5$).\n\nOutput a single integer: the answer to the problem, modulo $10^9 + 7$.\n\nFor the first sample, there are four possible pairs of $(c', d')$.\n\nIf $(c', d') = (AA, A)$, then the flexibility is $0$.\n\nIf $(c', d') = (AB, A)$, then the flexibility is $0$.\n\nIf $(c', d') = (AA, B)$, then the flexibility is $2$, as the pairs of binary strings $(1, 11)$, $(0, 00)$ are the only good pairs.\n\nIf $(c', d') = (AB, B)$, then the flexibility is $0$.\n\nThus, the total flexibility is $2$.\n\nFor the second sample, there are $2^1 + 2^2 + ... + 2^{10} = 2046$ possible binary strings of length not greater than $10$, and the set of pairs of good strings is precisely the set of pairs $(s, s)$, where $s$ is a binary string of length not greater than $10$.\n\n## Input\n\nThe first line contains the string $c$ ($1 ≤ |c| ≤ 3·10^5$).The second line contains the string $d$ ($1 ≤ |d| ≤ 3·10^5$).The last line contains a single integer $n$ ($1 ≤ n ≤ 3·10^5$).\n\n## Output\n\nOutput a single integer: the answer to the problem, modulo $10^9 + 7$.\n\n[samples]\n\n## Note\n\nFor the first sample, there are four possible pairs of $(c', d')$.If $(c', d') = (AA, A)$, then the flexibility is $0$.If $(c', d') = (AB, A)$, then the flexibility is $0$.If $(c', d') = (AA, B)$, then the flexibility is $2$, as the pairs of binary strings $(1, 11)$, $(0, 00)$ are the only good pairs.If $(c', d') = (AB, B)$, then the flexibility is $0$.Thus, the total flexibility is $2$.For the second sample, there are $2^1 + 2^2 + ... + 2^{10} = 2046$ possible binary strings of length not greater than $10$, and the set of pairs of good strings is precisely the set of pairs $(s, s)$, where $s$ is a binary string of length not greater than $10$.","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ c, d \\in \\{A, B, ?\\}^* $ be input strings of lengths $ |c|, |d| \\geq 1 $, and let $ n \\in \\mathbb{Z}^+ $ be a positive integer.  \nLet $ \\Sigma = \\{A, B\\} $.  \nFor any string $ x \\in \\{A, B, ?\\}^* $, define $ \\text{expand}(x) $ as the set of strings in $ \\Sigma^{|x|} $ obtained by replacing each $ ? $ in $ x $ with either $ A $ or $ B $.  \n\nA pair of strings $ (s, t) \\in \\Sigma^* \\times \\Sigma^* $ is called *good* with respect to $ (x, y) \\in \\Sigma^* \\times \\Sigma^* $ if:  \n- $ s $ is a string over $ \\{0,1\\} $,  \n- $ t $ is a string over $ \\{0,1\\} $,  \n- Replacing every $ A $ in $ x $ with $ s $ and every $ B $ in $ x $ with $ t $ yields the same string as replacing every $ A $ in $ y $ with $ s $ and every $ B $ in $ y $ with $ t $.  \nFormally, define the *substitution map* $ \\phi_{s,t}: \\{A,B\\}^* \\to \\{0,1\\}^* $ by:  \n$$\n\\phi_{s,t}(A) = s, \\quad \\phi_{s,t}(B) = t\n$$  \nThen $ (s,t) $ is *good* for $ (x,y) $ iff $ \\phi_{s,t}(x) = \\phi_{s,t}(y) $.  \n\nThe *flexibility* of a pair $ (x,y) \\in \\Sigma^* \\times \\Sigma^* $ is:  \n$$\n\\text{flex}(x,y) = \\left| \\left\\{ (s,t) \\in \\bigcup_{k=1}^n \\{0,1\\}^k \\times \\bigcup_{k=1}^n \\{0,1\\}^k \\ \\middle|\\ \\phi_{s,t}(x) = \\phi_{s,t}(y) \\right\\} \\right|\n$$\n\n**Constraints**  \n1. $ 1 \\leq |c|, |d| \\leq 3 \\cdot 10^5 $  \n2. $ 1 \\leq n \\leq 3 \\cdot 10^5 $  \n3. $ c, d $ contain only characters from $ \\{A, B, ?\\} $  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{\\substack{c' \\in \\text{expand}(c) \\\\ d' \\in \\text{expand}(d)}} \\text{flex}(c', d') \\mod (10^9 + 7)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF794G","tags":["combinatorics","dp","math"],"sample_group":[["A?\n?\n3","2"],["A\nB\n10","2046"]],"created_at":"2026-03-03 11:00:39"}}