#include <bits/stdc++.h>
using namespace std;
// typedef long long lld;
#define int long long
const int p = 1e9 + 7;
const int N = 1000005;
string s, t;
vector<int> op1, op;
int k, inv3; 
const int h[] = {1, 2, 4, 3};
int fcalc[N], fc[N];

int powe(int a, int b) {
    int base = 1;
    while(b) {
        if(b & 1) base = base * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return base;
}

int calc(int n) {
    if(n == op.size()) return 1;
    if(fcalc[n]) return fcalc[n];
    else return fcalc[n] = (calc(n + 1) * 4 + 1) % p;
}

inline int S(int sufz) {
    return (fc[sufz] - 4) % p * inv3 % p;
} 

int getans(int n) {
    if(n == op.size() - 1) {
        return h[op[n]];
    }
    int pertot = (h[op[n]] - 1) * calc(n + 1) % p;
    return (pertot + getans(n + 1)) % p;
}

void solve() {
    op.clear();
    cin >> s >> t >> k;
    int n = max(s.size(), t.size());
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    if(n % 2) n++;
    // s.resize(n); t.resize(n);
    while(s.size() < n) s.push_back('0');
    while(t.size() < n) t.push_back('0');
    for(int i = 0; i < n; i++) {
        op1.push_back((s[i] - '0') ^ (t[i] - '0'));
    }
    reverse(op1.begin(), op1.end());
    for(int i = 0; i < n; i += 2) {
        op.push_back(op1[i] * 2 + op1[i + 1]);
    }
    int ans = getans(0) - 1;
    int sufz = 0;
    for(int i = op.size() - 1; op[i] == 0; i--) sufz++;
    if(k  > sufz + 1 && sufz < op.size()) ans = -1;
    else ans = (ans + S(k)) % p;
    cout << ans << "\n";
}


signed main() {
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    fc[0] = 1; inv3 = powe(3, p - 2);
    
    for(int i = 1; i < N; i++) {
        fc[i] = fc[i - 1] * 4 % p;
    }
    int T; cin >> T;
    while(T--) solve();
    return 0;
}