#4967. 未命名的签到题

内存限制:256 MiB 时间限制:40 Sec

题目描述

给定两个只含大写字母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。

输入格式

三行,依次为字符串c,d和常数n,它们的意义如上所述。
1<=|c|,|d|<=3*10^5,1<=n<=10^10

输出格式

输出仅一行,表示Sigma(f(x,y))在模10^9+7下的取值。

样例

样例输入


			
```
A?
?
3
```

样例输出


			
```
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。

数据范围与提示