304141: CF794G. Replace All
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Replace All
题意翻译
给两个包含`A`,`B`,`?`的串,`?`可以是`A`或`B`,求所有`?`的情况下,求下面这个东西的和:统计有多少对长度$\le n$的01串(S,T)使得把所有`A`换成S,`B`换成T使得两个串相等题目描述
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 $ 10^{9}+7 $ .输入输出格式
输入格式
The first line contains the string $ c $ ( $ 1<=|c|<=3·10^{5} $ ). The second line contains the string $ d $ ( $ 1<=|d|<=3·10^{5} $ ). The last line contains a single integer $ n $ ( $ 1<=n<=3·10^{5} $ ).
输出格式
Output a single integer: the answer to the problem, modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
A?
?
3
输出样例 #1
2
输入样例 #2
A
B
10
输出样例 #2
2046