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.
Output
Output a single integer: the answer to the problem, modulo
109+7.
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.