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