#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#define dbg(x) cerr<<"In the line "<<__LINE__<<": the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In the line "<<__LINE__<<": the "<<#x<<" = "<<x<<" ; the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef long long ll;
template<typename T>
T &read(T &r){
	r=0;bool w=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar();
	return r=w?-r:r;
}
const int mod=1000000007;
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int del(int x,int y){return x<y?(x-y+mod):(x-y);}
inline void cadd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void cdel(int &x,int y){x=x<y?(x-y+mod):(x-y);}
const int N=1000100;
char s[N],t[N];
int a[N];
int k;
int fpow[N];
pii pls(pii x,pii y){
	//(*x.fi + x.se)*y.fi + y.se
	return mp(1ll*x.fi*y.fi%mod, add(1ll*x.se*y.fi%mod,y.se));
}
int qpow(int k){
	--k;
	pii s=mp(0,1),a=mp(4,1);
	while(k){
		if(k&1)s=pls(s,a);
		a=pls(a,a);
		k>>=1;
	}
	return add(s.fi,s.se);
}
void getstr(char *str){
	char c=getchar();
	int tot=0;
	while(c!='0'&&c!='1')c=getchar();
	while(c=='0'||c=='1')str[++tot]=c,c=getchar();
	str[tot+1]=0;
}
void solve(){
	getstr(s);
	getstr(t);
	read(k);
	int n=strlen(s+1),m=strlen(t+1);
	int len=max(n,m);
	for(int i=1;i<=len;i++)a[i]=0;
	for(int i=1;i<=n;i++)a[len-n+i]=s[i]-'0';
	for(int i=1;i<=m;i++)a[len-m+i]^=t[i]-'0';
	//(__builtin_ctz(x)-1)/2+1
	int p=-1;
	for(int i=n;i>=1;i--){
		if(a[i]){
			p=i;
			break;
		}
	}
	if(p!=-1){
		p=n-p;
		//
		if((p-1)/2+1<k){
			puts("-1");
			return ;
		}
	}
	n=len;
	int ans=0;
	for(int i=1;i<=n;i++)
		if(a[i]){
			cadd(ans,fpow[n-i+1]);
			a[i]^=1;
			if((n-i+1)%2==0)a[i+1]^=1;
		}
	cadd(ans,qpow(k));
	cdel(ans,1);
	cout<<ans<<'\n';
}
signed main(){
	fpow[1]=1;
	for(int i=2;i<=1000001;i++){
		if(i%2==0)fpow[i]=2ll*fpow[i-1]%mod;
		else fpow[i]=add(2ll*fpow[i-1]%mod,1);
	}
	int T;read(T);while(T--)solve();
	return 0;
}