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 109<=+<=7.
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 a single integer: the answer to the problem, modulo 109<=+<=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<sup class="upper-index">1</sup> + 2<sup class="upper-index">2</sup> + ... + 2<sup class="upper-index">10</sup> = 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.