#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=1e9+7;
int n;
ll dp[1000001];
ll pw(ll x,ll y){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1)%mod;
	ll res=pw(x,y/2);
	return res*res%mod;
}
void solve(){
	string s,t;ll k;
	cin >> s >> t >> k;
	reverse(s.begin(),s.end());
	reverse(t.begin(),t.end());
	int n=max(s.size(),t.size());
	if(n%2) ++n;
	s.resize(n,'0');
	t.resize(n,'0');
	bool ugly=true;
	for(int i=0; i<n ;i++){
		s[i]^=t[i]%2;
		if(s[i]%2) ugly=false;
	}
	if(ugly){
		ll res=(pw(4,k)+mod-4)%mod;
		res=res*pw(3,mod-2)%mod;
		cout << res << '\n';
		return;
	}
	n/=2;
	int m=0;
	while(s[2*m]=='0' && s[2*m+1]=='0') m++;
	if(k>m+1){
		cout << "-1\n";
		return;
	}
	dp[0]=0;
	for(int i=1; i<=n ;i++) dp[i]=(dp[i-1]*4+4)%mod;
	ll base=0;
	for(int i=m; i<n ;i++){
		int frog=(s[2*m+1]-'0')*2+(s[2*m]-'0');
		if(frog>=2) frog^=1;
		base=(base+frog*(dp[i]+1))%mod;
	}
	ll ans=(base+dp[k-1])%mod;
	cout << ans << '\n';	
}
int main(){
	ios::sync_with_stdio(false);
	int t;cin >> t;while(t--) solve();
}