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⁹ + 7.

The first line contains the string c (1 ≤ |c| ≤ 3·10⁵).

The second line contains the string d (1 ≤ |d| ≤ 3·10⁵).

The last line contains a single integer n (1 ≤ n ≤ 3·10⁵).

Output a single integer: the answer to the problem, modulo 10⁹ + 7.