#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 });

vector<array<int, 4> > f(MAXN);

i64 find(int i, int x) {
    if (f[i][x])
        return f[i][x];
    if (i == 0) {
        return f[i][x] = mp[x];
    }
    return f[i][x] = (find(i - 1, x) * 4ll % mod + mp[x]) % 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.push_back(ss[i * 2] + ss[i * 2 + 1] * 2);
    // for (auto i : four)
    //     cerr << i;
    // cerr << endl;

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

    i64 cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += !four[i];

    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);

    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}