#include <bits/stdc++.h>
#define int long long
#define N 1000009
#define mod 1000000007
using namespace std;

int qpow(int mt, int p) {
	int ret = 1;
	for (; p; mt = mt * mt % mod, p >>= 1)
		if (p & 1)
			ret = ret * mt % mod;
	return ret;
}

int F(int x) {
	return (qpow(4, x) + mod - 4) * qpow(3, mod - 2) % mod;
}
char a[N], b[N];
int k;
int f[N];

int calc(char x, char y) {
	if (x == '0' && y == '0')
		return 0;
	if (x == '1' && y == '0')
		return 1;
	if (x == '1' && y == '1')
		return 2;
	if (x == '0' && y == '1')
		return 3;
	return 114514;
}
int lena, lenb;

int solve() {
	scanf("%s%s%lld", a, b, &k);
	lena = strlen(a), lenb = strlen(b);
	a[lena] = '0';
	b[lenb] = '0';
	for (int i = 0; i < lena / 2; i++)
		swap(a[i], a[lena - 1 - i]);
	for (int i = 0; i < lenb / 2; i++)
		swap(b[i], b[lenb - 1 - i]);
	lena = max(lena, lenb);
	for (int i = 0; i < lena; i++)
		if (b[i] == '1') {
			if (a[i] == '0')
				a[i] = '1';
			else if (a[i] == '1')
				a[i] = '0';
		}
	while (lena >= 1 && a[lena - 1] == '0')
		lena--;
	if (lena == 0)
		return F(k);
	if (lena <= 2)
		return k >= 2 ? -1 : calc(a[0], a[1]);
	bool flag = 1;
	for (int i = 0; i + 2 < lena; i += 2)
		if (a[i] == '1' || a[i + 1] == '1')
			flag = 0;
	if (flag == 1) {
		if (k >= 3)
			return -1;
		else {
			int ans = calc(a[(lena - 1) / 2 * 2],
			               a[(lena - 1) / 2 * 2 + 1]) * (f[(lena - 1) / 2 + 1] + 1) + (k == 2) * f[(lena - 1) / 2 + 1 ];
			return ans % mod;
		}
	} else {
		if (k >= 2)
			return -1;
		int ans = 0;
		for (int i = (lena - 1) / 2 * 2; i >= 0; i -= 2) {
			ans = (ans + (f[i / 2 + 1 ] + 1) * calc(a[i], a[i + 1])) % mod;
		}
		return ans;
	}

	return 114514;
}

signed main() {
	fill(a, a + N, '0');
	fill(b, b + N, '0');
	for (int i = 1; i < N; i++)
		f[i] = F(i);
	int t;
	scanf("%lld", &t);
	while (t--) {
		printf("%lld\n", solve());
		for (int i = 0; i < lena; i++)
			a[i] = b[i] = '0';
	}
}
/*
5
1 10 1
1 10 2
100 0 2
11 11 3
1111 0 1
*/