记录编号	445230	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Codeforces 794G] 文本替换	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	9.104 s
提交时间	2017-09-05 16:27:36	内存使用	14.62 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const int SIZE=300000;
LL realmod(LL a,LL M){
	a%=M;
	if(a<0) a+=M;
	return a;
}
LL quickpow(LL a,LL n,LL M){
	a=realmod(a,M);
	LL ans=1;
	while(n){
		if(n&1) ans=ans*a%M;
		a=a*a%M;
		n>>=1;
	}
	return ans;
}
LL fact[SIZE*2+10]={0};
LL invfact[SIZE*2+10]={0};
LL phi[SIZE+10]={0};
LL phi_sum[SIZE+10]={0};
void phi_table(LL n){
	LL i,j;
	phi[1]=1;
	for(i=2;i<=n;i++){
		if(!phi[i]){
			for(j=i;j<=n;j+=i){
				if(!phi[j]) phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
		}
	}
	phi_sum[0]=0;
	for(int i=1;i<=n;i++) phi_sum[i]=(phi_sum[i-1]+phi[i])%MOD;
}
LL inverse(LL a,LL p){//p must be prime
	return quickpow(a,p-2,p);
}
void prepare_fact(LL n){
	fact[0]=invfact[0]=1;
	for(LL i=1;i<=n;i++){
		fact[i]=realmod(fact[i-1]*i,MOD);
		invfact[i]=inverse(fact[i],MOD);
	}
}
LL Comb(LL n,LL m){//n select m
	assert(n>=m);
	//n!/(m!*(n-m)!)
	LL ans=fact[n];
	ans=realmod(ans*invfact[m],MOD);
	ans=realmod(ans*invfact[n-m],MOD);
	return ans;
}
LL N;
char C[SIZE+10],D[SIZE+10];
LL gcd(LL a,LL b){
	return !b?a:gcd(b,a%b);
}
LL calc_basic(LL x, LL y){//situation 1(basic), where |s|:|t| is known. x,y indicates "minimum representation"
	if(x==0||y==0) return 0;//cannot be x==y==0(see solve())
	if(x<0) x*=-1,y*=-1;
	if(x<0||y<0) return 0;
	//s repeat x times = t repeat y times
	//|s|:|t|=y:x
	LL g=gcd(x,y);
	LL k=N/max(x/g,y/g);//the length of "kernel" can be 1..k
	//so the answer is 2^1+...+2^k=2*(2^k-1)
	return realmod(2*(quickpow(2,k,MOD)-1),MOD);
}
LL calc_free(void){//situation 2(free): s and t can be arbitrarily selected.
	//something like "AAB - AAB"
	//(2^1+...+2^N)^2=(2*(2^N-1))^2
	LL sn=realmod(2*(quickpow(2,N,MOD)-1),MOD);
	LL ans = sn*sn%MOD;
	return ans;
}
LL free_cnt(void){
	int n=strlen(C),m=strlen(D);
	if(n!=m) return 0;
	LL ans=1;
	for(int i=0;i<n;i++){
		char a=C[i],b=D[i];
		if(a=='?'&&b=='?'){
			ans=realmod(ans*2,MOD);
		}
		else if(a=='?'||b=='?'){}
		else if(a!=b) return 0;
	}
	return ans;
}
LL calc_sync(void){//situation 3: s and t can be arbitrary, but they have a common "kernel"
	//it's sum(sum(2^gcd(i,j)))
	LL ans=0;
	for(int g=1;g<=N;g++){
		LL cnt=phi_sum[N/g]*2-1;
		LL now=quickpow(2,g,MOD);
		ans+=cnt*now%MOD;
		ans%=MOD;
	}
	return ans;
}
LL solve(LL a,LL d1,LL b,LL d2){
	//a 'A' and d1 '?' on LHS
	//b 'B' and d2 '?' on RHS
	//(after obvious elimination)
	//d1 '?' can serve as A on LHS or minus B on RHS
	//d2 '?' can serve as minus A on LHS or B on RHS
	//so after apply all '?', (A on LHS) - (B on RHS) = a+d1-(b+d2)
	//LHS is at least a-d2 and at most a+d1
	LL sync_flx=calc_sync();
	LL free_flx=calc_free();
	LL cnt=free_cnt();
	LL ans=0;
	for(LL aa=a-d2;aa<=a+d1;aa++){
		//in all d1+d2 '?', there are aa-a+d2 turned
		LL bb=aa-(a+d1-b-d2);
		LL t=Comb(d1+d2,aa-a+d2);
		if(aa==0&&bb==0){
			LL now=realmod((t-cnt)*sync_flx%MOD + cnt*free_flx%MOD, MOD);
			ans=realmod(ans+now,MOD);
		}
		else{
			ans=realmod(ans+t*calc_basic(aa,bb)%MOD,MOD);
		}
	}
	return ans;
}
void work(void){
	LL a=0,d1=0,b=0,d2=0;
	int n=strlen(C),m=strlen(D);
	for(int i=0;i<n;i++){
		if(C[i]=='A') a++;
		else if(C[i]=='B') b--;
		else if(C[i]=='?') d1++;
	}
	for(int i=0;i<m;i++){
		if(D[i]=='A') a--;
		else if(D[i]=='B') b++;
		else if(D[i]=='?') d2++;
	}
	LL ans=solve(a,d1,b,d2);
	cout<<ans<<endl;
}
void read(void){
	scanf("%s",C);
	scanf("%s",D);
	scanf("%I64d",&N);
}
int main(){
	freopen("replaceall.in","r",stdin);
	freopen("replaceall.out","w",stdout);
	//freopen("D:/MinGWStudio/Templates/DATA/duipai/input.in","r",stdin);
	//freopen("input.in","r",stdin);
	phi_table(SIZE);
	prepare_fact(SIZE*2);
	read();
	work();
	return 0;
}