2793. [Codeforces 794G] 文本替换

【题目描述】

分析师Igor正在研究文本编辑器的“文本替换”功能。他闲得无聊，想出了以下问题：

给定两个仅含大写字母'A'和'B'的英文字符串。称一对字符串(s,t)是“好”的，当且仅当：

1. s和t仅包含'0'和'1'

2. 1<=|s|,|t|<=n，其中|s|是s的长度

3. 如果把x和y中的所有'A'替换成s，所有'B'替换成t，那么x和y会变得一样。

例如，如果x=AAB,y=BB,n=4,那么(01,0101)是一组好字符串，因为替换后x和y都变成了“01010101”.

称一对字符串(x,y)的“自由度”是相应好字符串对(s,t)的数量。这里都是有序对，例如(0,1)和(1,0)不同。

给定两个字符串c和d，它们由'A','B'，'?'组成。'?'可以表示'A'或'B'，问所有情况下的自由度之和。

【输入格式】

前两行各一个字符串c,d（1<=长度<=3*10^5）

第三行一个正整数N，满足1<=N<=3*10^5.

【输出格式】

一个整数，答案模10^9+7的值。

【样例输入】

A?

?

3

【样例输出】

【样例输入】

A

B

10

【样例输出】

【提示】

对于第一个样例，有四对可能的 (c', d').

若 (c', d') = (AA, A), 自由度为  0.

若 (c', d') = (AB, A), 自由度为 0.

若 (c', d') = (AA, B), 自由度为 2, 两种方案是 (1, 11), (0, 00) .

若 (c', d') = (AB, B), 自由度为 0.

所以总自由度为2.

对于第二个样例，长度不超过10的01串共有2^1+...+2^10=2046个，而所有好字符串对形如(s,s)，其中s是长度不超过10的01串。

【来源】

CODEFORCES ROUND #414

http://codeforces.com/contest/794/problem/G