#include <bits/stdc++.h>
#define int long long

typedef long long ll;

const int mod = 1e9 + 7;

void solve(){
    std::string s, t; std::cin >> s >> t;
    int k;  std::cin >> k;
    std::reverse(s.begin(), s.end());
    std::reverse(t.begin(), t.end());
    while (s.size() < t.size())
        s.push_back('0');
    while (t.size() < s.size())
        t.push_back('0');
    while (s.size() % 2) {
        s.push_back('0');
        t.push_back('0');
    }
    std::vector<int> a(s.size() / 2, 0);
    int num = 0; bool f = true;
    for (int i = 0; i < s.size(); i++) {
        int tmp = (s[i] - '0') ^ (t[i] - '0');
        if (tmp == 0 && f) {
            num++;
        } else f = false;
        if (i & 1) {
            a[i / 2] |= (tmp << 1);
        } else {
            a[i / 2] |= tmp;
        }
    }
    if (num + 1 < k) {
        std::cout << "-1\n";
        return;
    }
    std::vector<int> arr = {0, 1, 3, 2};
    int now = 1;
    ll ans = 0;
    for (int i = 0; i < a.size(); i++) {
        ans = (ans + now * arr[a[i]]) % mod;
        now = (4LL * now + 1) % mod;
    }
    now = 4;
    for (int i = 0; i < k - 1; i++) {
        ans = (ans + now) % mod;
        now = (4LL * now) % mod;
    }
    std::cout << ans << "\n";
}

signed main(){

#ifdef Onlion_Judge
    freopen("IO/input.in", "r", stdin);
    freopen("IO/output.out", "w", stdout);
    // freopen("E:\\save work\\data\\4.in", "w", stdout);
#endif

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // std::cout.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
}