#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e6 + 10;
const int inf = 1e9;
const int mod = 1e9 + 7;

int qpow(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}

void solve() {
	string s, t;
	int k;
	cin >> s >> t >> k;
	reverse(s.begin(), s.end());
	reverse(t.begin(), t.end());
	int ans = 4 * (qpow(4, k - 1) - 1) % mod;
	(ans *= qpow(3, mod - 2)) %= mod;
	int lens = s.size(), lent = t.size();
	if(lens <= lent) {
		for(int i = lens + 1; i <= lent; i++) {
			s.push_back('0');
		}
	}
	else {
		for(int i = lent + 1; i <= lens; i++) {
			t.push_back('0');
		}	
	}
	int len = max(lens, lent);
	vector<char> c(max(lens,lent));
	for(int i = 0; i < max(lens, lent); i++) {
		c[i] = s[i] == t[i] ? '0' : '1';
	}
	int cnt = 0;
	for(char i: c) {
		if(i == '1')break;
		cnt++;
	}
	if(k > cnt / 2 + 1 && cnt != max(lens, lent)) {
		cout << -1 << endl;
		return;
	}
	if(len % 2 == 1) {
		c[len++] = '0';
	}
	// for(int i = 0; i < len; i++) {
	// 	cout << c[i] ;
	// }
	// cout << endl;
	// cout << ans << endl;
	vector<int> p(N);
	p[0] = 1;
	for(int i = 1; i < N; i++) {
		p[i] = p[i - 1] * 4 % mod;
	}
	for(int i = 1; i < N; i++) {
		(p[i] += p[i - 1]) %= mod;
	}
	for(int i = 0; i + 1 < len; i += 2) {
		int x = i + 1;
		// if(c[i] == '0' && c[i + 1] == '0') {
		// 	(ans += 1) %= mod;
		// }
		// else
		if(c[i] == '0' && c[i + 1] == '1') {
			(ans += 3 * p[x / 2]) %= mod;
		}
		else if(c[i] == '1' && c[i + 1] == '0') {
			(ans += p[x / 2]) %= mod;
		}
		else if(c[i] == '1' && c[i + 1] == '1'){
			(ans += 2 * p[x / 2]) %= mod;
		}
	}
	cout << ans % mod << endl;
}
#undef int
int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}
}