#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using uint=unsigned;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define si(x) int(x.size())
#define a first
#define b second
template<class t>using vc=vector<t>;

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b; return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(a>b){a=b; return true;}else return false;}

template<class t,class u>
ostream& operator<<(ostream&os,const pair<t,u>&p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}
template<class t>ostream& operator<<(ostream&os,const vector<t>&v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

const uint mod = 1000000007;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint&operator+=(mint r){return s(v+r.v);}
	mint&operator-=(mint r){return s(v+mod-r.v);}
	mint&operator*=(mint r){v=(unsigned long long)v*r.v%mod;return *this;}
	mint&operator/=(mint r){return *this*=r.inv(); }
	mint operator+(mint r)const{return mint(*this)+=r;}
	mint operator-(mint r)const{return mint(*this)-=r;}
	mint operator*(mint r)const{return mint(*this)*=r;}
	mint operator/(mint r)const{return mint(*this)/=r;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1) res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};

using P=pair<int,int>;

int f(const string &s,int i){
	int ret=0;
	if(2*i<s.size())ret+=s[2*i]-'0';
	if(2*i+1<s.size())ret+=(s[2*i+1]-'0')*2;
	return ret;
}

void solve(){
	string s,t;
	int k;
	cin>>s>>t>>k;
	
	reverse(s.begin(),s.end());
	reverse(t.begin(),t.end());
	
	vector<int> a((max(s.size(),t.size())+1)/2);
	for(int i=0;i<(max(s.size(),t.size())+1)/2;i++){
		a[i]=f(s,i)^f(t,i);
	}
	while(a.size()>0&&a.back()==0)a.pop_back();
	if(a.size()==0){
		if(k==1){
			cout<<0<<endl;
			return;
		}
		mint ret=mint(4).pow(k-1);
		ret-=1;
		ret/=3;
		ret*=4;
		cout<<ret.v<<endl;
		return;
	}
	mint ret=0;
	mint u=1;
	k--;
	rep(i,a.size()){
		if(a[i]==0){
			if(k==1)ret+=u*4;
			k--;
		}
		else if(a[i]==1){
			ret+=u;
		}
		else {
			ret+=u*(5-a[i]);
		}
		u=u*4+1;
	}
	if(k>0)cout<<-1<<endl;
	else cout<<ret.v<<endl;
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int T;
	cin>>T;
	rep(t,T)solve();
}