CF794G.Replace All

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 $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 $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$ .