#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using pll = pair<ll,ll>;
using vi = vector<int>;

#define fr first 
#define sc second

using ld = long double;

#define all(x) (x).begin(), (x).end()

const int maxn = 1e6+10, inf = 1e9+100;
const ll linf = 8e18+100;
const int mod = 1e9+7;



//  #define cerr if(0) cerr

ll po(ll a,ll b){
	ll ans = 1;
	for(a%=mod;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}

ll inv(ll a){
	return po(a,mod-2);
}

ll num4s(ll n){
	return (po(4,n+1)-1)*inv(3)%mod;
}

void solve () {
	string s,t;
	ll k;
	cin >> s >> t >> k;
	reverse(all(s));
	reverse(all(t));
	s.resize(max(s.size(),t.size()), '0');
	t.resize(s.size(), '0');
	for(int i=0;i<s.size();i++)s[i]^=t[i];
	if(s.size()%2)s.push_back(0);
	int numdz = 0;
	bool iszero = true;
	// for(int i=0;i<s.size();i++)cerr << int(s[i]) << " ";
	for(int i=0;i<s.size();i++){
		
		if(s[i]==0)numdz++;
		else {
			iszero = false;
			break;
		}
	}
	// cerr << endl;
	numdz /= 2;
	k--;
	if(iszero) {
		ll ans =  ( num4s(k)-1)%mod;
		if(ans<0)ans+=mod;
		cout << ans << "\n";
		return;
	}
	if(k>numdz){
		cout << "-1\n";
		return;
	}
	ll ans = 0;
	for(int i=numdz;i*2<s.size();i+=2){
		int num = s[2*i+1]*2+(s[2*i+1]^s[2*i]);
		ans = (ans + num * num4s(i)) %mod;
	}
	ans =  (ans + num4s(k)-1)%mod;
	if(ans<0)ans+=mod;
	cout << ans << "\n";
}


int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout<<fixed;
  cout.precision(20);
	int tc;
	cin >> tc;
	while(tc--)
  solve();
}