#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using i64 = long long;

const i64 mod = 1e9 + 7;
const int MAXN = 1e6 + 5;
using bs = bitset<MAXN>;

vector<int> mp({ 0, 1, 3, 2 });

int f[MAXN][4];


void init() {

    for (int i = 1; i <= 1000000; i++) {
        f[i][1] = f[i - 1][1] * 4 + 1;
        f[i][1] %= mod;
        f[i][2] = f[i - 1][1] * 4 + 3;
        f[i][2] %= mod;
        f[i][3] = f[i - 1][1] * 4 + 2;
        f[i][3] %= mod;
    }

}

i64 kpow(i64 x, i64 y) {
    i64 res = 1ll;
    while (y) {
        if (y & 1)
            res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

const i64 inv3 = kpow(3, mod - 2);

void solve() {
    string s, t;
    i64 k;
    cin >> s >> t >> k;
    bs ss(s), tt(t);
    ss ^= tt;
    // for (int i = 0; i < 10; i++)
    //     cerr << ss[i];
    // cerr << endl;

    int n = (max(s.length(), t.length()) + 1) >> 1;

    vector <int> four(0);
    // cerr << n << endl;
    for (int i = 0; i < n; i++)
        four.emplace_back(ss[i * 2] + ss[i * 2 + 1] * 2);

    n = four.size();
    i64 ans = 0;
    for (int i = 0; i < n; i++)
        if (four[i])
            ans += f[i][four[i]];

    i64 cnt = 0;
    int w = 0;
    while (four[w++] == 0) {
        cnt++;

    }

    if (ss.none()) {
        k--;
        cout << ((kpow(4ll, k + 1) - 4ll + mod) % mod * inv3 % mod) % mod << endl;
        return;
    }

    if (cnt + 1 < k) {
        cout << "-1\n";
        return;
    }

    if (s != t)
        k--;
    ans = (ans + (kpow(4ll, k + 1) - 4ll + mod) % mod * inv3 % mod) % mod;

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    f[0][0] = 0;
    f[0][1] = 1;
    f[0][2] = 3;
    f[0][3] = 2;
    init();
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}