#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i64 = long long;
using pii = pair<int, int>;
using db = double;

#define cY cout << "YES\n"
#define cN cout << "NO\n"
#define cA cout << ans << "\n"
#define pb push_back

const ll mod = 998244353;
const ll MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int mp[4][4];

void init() {
    mp[0][0] = 4;
    mp[0][1] = 1;
    mp[0][2] = 3;
    mp[0][3] = 2;

    mp[1][1] = 4;
    mp[1][0] = 1;
    mp[1][2] = 2;
    mp[1][3] = 3;

    mp[2][2] = 4;
    mp[2][3] = 1;
    mp[2][1] = 2;
    mp[2][0] = 3;

    mp[3][3] = 4;
    mp[3][2] = 1;
    mp[3][0] = 2;
    mp[3][1] = 3;
}

ll power(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}

void crossparallel() {
    string s, t;
    cin >> s >> t;

    int k;
    cin >> k;

    if (s == t) {
        ll ans = (power(4, k) - 1) * power(3, MOD - 2) - 1;
        ans = ans % MOD;
        cout << ans << "\n";
        return;
    }

    int len = std::max(s.size(), t.size());
    len += len & 1;

    std::string tmp = std::string(len - (int)s.size(), '0');
    s = tmp + s;
    tmp = std::string(len - (int)t.size(), '0');
    t = tmp + t;

    std::ranges::reverse(s), std::ranges::reverse(t);

    int pos = -1;
    for (int i = 1; i < min(s.size(), t.size()); i += 2) {
        if (s[i] != t[i] || s[i - 1] != t[i - 1])
            pos = i;
    }

    int cnt = 0;
    for (int i = 1; i <= pos; i += 2) {
        if (s[i] != t[i] || s[i - 1] != t[i - 1])
            i = i;
        else
            cnt++;
    }

    if (cnt < k - 1 || k > (pos + 1) / 2) {
        cout << -1 << "\n";
        return;
    }

    ll ans = (power(4, k) - 1) * power(3, MOD - 2) - 1;

    ll cur = 1;
    for (int i = 1; i <= pos; i += 2) {
        if (s[i] != t[i] || s[i - 1] != t[i - 1]) {
            int x = (s[i] - '0') * 2 + (s[i - 1] - '0');
            int y = (t[i] - '0') * 2 + (t[i - 1] - '0');
            ans += cur * mp[x][y];
            ans %= MOD;
        }
        cur = (cur << 2) + 1;
        cur %= MOD;
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int t = 1;
    cin >> t;
    while (t--) {
        crossparallel();
    }
    return 0;
}