#include<bits/stdc++.h>
using namespace std;
#define int long long
string s,t;
int _,O=1e9+7,k,n,a[1<<20],c,x,A;
int P(int x,int y){
	int z=1;
	for(;y;y/=2,x=x*x%O)
		if(y&1)
			z=z*x%O;
	return z;
}
void Z(){
	cin>>s>>t>>k;
	if(s==t){
		cout<<(P(4,k)-4+O)*P(3,O-2)%O<<'\n';
		return;
	}
	reverse(s.begin(),s.end());
	if(s.size()<t.size())
		swap(s,t);
	if(s.size()&1)
		s+='0';
	for(int i=0;i<t.size();i++)
		s[i]=((s[i]-'0')^(t[i]-'0'))+'0';
	n=0;
	for(int i=0;i<s.size();i+=2)
		a[++n]=(s[i]-'0')+(s[i+1]-'0')*2;
	c=0,k--;
	for(int i=1;i<=n;i++)
		if(!a[i])
			c++;
		else
			break;
	if(k>c){
		cout<<-1<<'\n';
		return;
	}
	x=1;
	for(int i=1;i<=k;i++)
		(A+=4*x)%=O,(x+=P(4,i))%=O;
	x=1;
	for(int i=1;i<=n;i++){
		if(a[i]==1)
			(A+=x)%=O;
		else if(a[i]==3)
			(A+=2*x)%=O;
		else if(a[i]==2)
			(A+=3*x)%=O;
		(x+=P(4,i))%=O;
	}
	cout<<A<<"\n";
}
signed main(){
	for(cin>>_;_--;)
		Z();
}4
1 10 1
0
1 10 2
4
100 0 2
13
11 11 3
20

answer.code:57:2: error: expected unqualified-id before numeric constant
   57 | }4
      |  ^