#include<bits/stdc++.h>
#define ll long long
#define int long long
#define pii pair<int, int>
#define pb push_back
#define pf push_front
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,b,a) for(int i=b;i>=a;--i)
const ll inf = 1145141919810;
using namespace std;
inline ll read() {
	ll x=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9') {
		if (c=='-')  f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void print(ll x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
	return ;
}
inline void pprint(ll x) {
	print(x);
	puts("");
}

vector<ll> fac, t;
const int mod = 1e9 + 7;

ll jz(ll x) {
	return (x % mod + mod) % mod;
}

void slv() {
	string s, t;
	ll k;
	vector<int> a;
	cin >> s >> t >> k;

	reverse(s.begin(), s.end());
	reverse(t.begin(), t.end());
	while(s.length() < t.length()) s += "0";
	while(s.length() > t.length()) t += "0";
	
	
	
	if(s.length() % 2 == 0) s += "0", t += "0";
	int len = s.length();
	for(int i = 0; i < len; i = i + 2) {
		string _s = "";
		
		if(s[i + 1] == t[i + 1]) _s += "0";
		else _s += "1";
		
		if(s[i] == t[i]) _s += "0";
		else _s += "1";

		if(_s == "00") a.pb(0);
		else if(_s == "01") a.pb(1);
		else if(_s == "11") a.pb(2);
		else if(_s == "10") a.pb(3);
	}
	while(a.size() && a[(int)a.size() - 1] == 0) a.pop_back();

	if(a.size() == 0) {
		cout << jz(fac[k - 1] - 1) << endl;
		return ;
	}
//	puts("----");
//	cout << a.size() << endl;
//	for(auto x:a) cout << x;
//	puts("\n----");
	int n = a.size(), st = -1, cnt = 0;
	for(int i = 0; i < n && a[i] == 0; ++i) st++;
//	cout << "st = " << st << endl;
	if(k > st + 2) {
		cout << -1 << endl;
		return;
	}

	ll ans = 0;
	//如果能走到，那么就硬走，直到走到0
	for(int i = n - 1; i > st; --i) {
		ans = (ans + fac[i] * a[i] % mod) % mod;
	}

	if(st > -1) ans = (ans + jz(fac[k - 1] - 1) % mod) % mod;
//	cout << "ans = " << ans << endl;
	pprint(jz(ans));
	//然后走完0就行了
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	fac.resize(2000000);
	
	fac[0] = 1;
	for(int i = 1; i <= 1999999; ++i) {
		fac[i] = fac[i - 1] * 4 % mod + 1;
		fac[i] %= mod;
	}


	int _ = read();
	while(_--) slv();
	return 0;
}
/*
1
11 11 3
*/