BZPRO

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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository