#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

const int N = 1e6;
const int Mod = 1e9 + 7;

ll ksm(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) {
            res = res * x % Mod;
        }
        x = x * x % Mod;
        y >>= 1;
    }
    return res;
}
ll inv(ll x) {
    return ksm(x, Mod - 2);
}

void solve() {
    string s, t; int k;
    cin >> s >> t >> k;

    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());

    if (SZ(s) < SZ(t)) {
        swap(s, t);
    }

    vector<int> p;
    p.resize(max(SZ(s), SZ(t)));
    for (int i = 0; i < SZ(t); i++) {
        p[i] = (s[i] - '0') ^ (t[i] - '0');
    }
    for (int i = SZ(t); i < SZ(s); i++) {
        p[i] = s[i] - '0';
    }

    int cnt0 = 0;
    while (cnt0 < SZ(p) && !p[cnt0]) {
        cnt0++;
    }
    if (cnt0 == SZ(p)) {
        int ans = 4 * (ksm(4, k - 1) - 1) % Mod * inv(3) % Mod;
        cout << ans << '\n';
        return ;
    }

    int c0 = cnt0 / 2 + 1;
    if (c0 < k) {
        cout << -1 << '\n';
        return ;
    }

    vector f(N + 1, 0);
    f[0] = 0; f[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (i % 2 == 0) {
            f[i] = 2 * f[i - 1] % Mod;
        } else {
            f[i] = (2 * f[i - 1] + 1) % Mod;
        }
    }

    ll pos = 0;
    for (int i = SZ(p) - 1; i >= 0; i--) {
        if (p[i] == 0) {
            continue;
        }

        if (i % 2 == 0) {
            pos = (pos + f[i + 1]) % Mod;
        } else {
            pos = (pos + f[i + 1]) % Mod;
            p[i - 1] ^= 1;
        }
    }

    // cout << "pos = " << pos << '\n';
    
    ll ans = (pos + 4 * (ksm(4, k - 1) - 1) % Mod * inv(3) % Mod) % Mod;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}