#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("");
}

const int mod = 1e9 + 7;
ll qm(ll a, ll b){
	ll base = 1;
	while(b){
		if(b & 1) base = base * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return base % mod;
}
ll inv(ll x){
	return qm(x, mod - 2);
}
ll fac(ll x){
	//fac_0 = 1
	return (qm(4, x + 1) - 1) * inv(3) % mod;
}
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() & 1) 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 ;
	}
	
	int n = a.size(), st = -1, cnt = 0;
	for(int i = 0; i < n && a[i] == 0; ++i) st++;
	if(k > st + 2) {
		cout << -1 << '\n';
		return;
	}

	ll ans = jz(fac(k - 1) - 1) % mod;
	for(int i = n - 1; i > st; --i) ans = (ans + fac(i) * a[i] % mod) % mod;
	
	cout << jz(ans) << '\n';
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int _ = read();
	while(_--) slv();
	return 0;
}
/*
1
11 11 3
*/