English · Original
Chinese · Translation
Formal · Original
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_ which consist of the English letters '_A_' and '_B_' only, a pair of strings (_s_, _t_) is called good if:
* _s_ and _t_ consist of the characters '_0_' and '_1_' only.
* 1 ≤ |_s_|, |_t_| ≤ _n_, where |_z_| denotes the length of string _z_, and _n_ is a fixed positive integer.
* 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.
For 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_".
The 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.
You'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.
## Input
The first line contains the string _c_ (1 ≤ |_c_| ≤ 3·105).
The second line contains the string _d_ (1 ≤ |_d_| ≤ 3·105).
The last line contains a single integer _n_ (1 ≤ _n_ ≤ 3·105).
## Output
Output a single integer: the answer to the problem, modulo 109 + 7.
[samples]
## Note
For 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 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.
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$ which consist of the English letters $A$ and $B$ only, a pair of strings $(s, t)$ is called $\text{good}$ if:
For 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".
The $\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.
You'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$.
The 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$).
Output a single integer: the answer to the problem, modulo $10^9 + 7$.
For 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$.
## Input
The 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$).
## Output
Output a single integer: the answer to the problem, modulo $10^9 + 7$.
[samples]
## Note
For 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$.
**Definitions**
Let $ c, d \in \{A, B, ?\}^* $ be input strings of lengths $ |c|, |d| \geq 1 $, and let $ n \in \mathbb{Z}^+ $ be a positive integer.
Let $ \Sigma = \{A, B\} $.
For 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 $.
A pair of strings $ (s, t) \in \Sigma^* \times \Sigma^* $ is called *good* with respect to $ (x, y) \in \Sigma^* \times \Sigma^* $ if:
- $ s $ is a string over $ \{0,1\} $,
- $ t $ is a string over $ \{0,1\} $,
- 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 $.
Formally, define the *substitution map* $ \phi_{s,t}: \{A,B\}^* \to \{0,1\}^* $ by:
$$
\phi_{s,t}(A) = s, \quad \phi_{s,t}(B) = t
$$
Then $ (s,t) $ is *good* for $ (x,y) $ iff $ \phi_{s,t}(x) = \phi_{s,t}(y) $.
The *flexibility* of a pair $ (x,y) \in \Sigma^* \times \Sigma^* $ is:
$$
\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|
$$
**Constraints**
1. $ 1 \leq |c|, |d| \leq 3 \cdot 10^5 $
2. $ 1 \leq n \leq 3 \cdot 10^5 $
3. $ c, d $ contain only characters from $ \{A, B, ?\} $
**Objective**
Compute:
$$
\sum_{\substack{c' \in \text{expand}(c) \\ d' \in \text{expand}(d)}} \text{flex}(c', d') \mod (10^9 + 7)
$$
API Response (JSON)
{
"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...",
"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...",
"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 $ ...",
"is_translate": false,
"language": "Formal"
}
]
}