只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
4967 - 未命名的签到题
给定两个只含大写字母A和B的字符串x和y，我们定义一个有序字符串对(a,b)是「优秀的」，当且仅当它满足以下条件： a和b只包含字符0和1； 1<=|a|,|b|<=n，其中n是给定的常数； 如果我们将x与y中的字符A用a替换，字符B用b替换，则替换后的x和y相等。 定义f(x,y)为优秀的有序对(a,b)的个数。 现在你有两个字符串c和d，它们只包含字符A，B和问号。你需要求出Sigma(f(x,y))， 其中(x,y)是分别将c和d中的所有问号任意替换为A或B得到的所有不同的字符串对。 答案模10^9+7。
Input
三行，依次为字符串c，d和常数n，它们的意义如上所述。 1<=|c|,|d|<=3*10^5，1<=n<=10^10
Output
输出仅一行，表示Sigma(f(x,y))在模10^9+7下的取值。
Examples
Input
``` A? ? 3 ```
Output
``` 2 ``` 对于样例数据，有4种可能的(x,y)： 若(x,y)=(AA,A)，则f(x,y)=0； 若(x,y)=(AB,A)，则f(x,y)=0； 若(x,y)=(AA,B)，则f(x,y)=2，对应的(a,b)分别为(1,11)和(0,00)； 若(x,y)=(AB,B)，则f(x,y)=0。