#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tag_and_trait.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// namespace gt = __gnu_pbds;
#define IS_MULTITEST 1

using namespace std;

#include "angel/math/modint.hpp"

#pragma region Macros
// clang-format off
using ll = long long; using uint = unsigned int; using ull = unsigned long long;
using i32 = int; using i64 = ll; using u32 = uint; using u64 = ull;
using i128 = __int128_t; using u128 = __uint128_t;
using Str = string;
template <class T> using Vec = vector<T>;
template <class T> using RevPriq = priority_queue<T, vector<T>, greater<T>>;
constexpr std::array<std::pair<int, int>, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};
constexpr std::array<std::pair<int, int>, 8> dxy8 = {
    {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}};
constexpr int inf32 = 1 << 30; constexpr ll inf64 = 1ll << 60;
constexpr char eoln = '\n';
#define L(i, l, r) for (int i = (l); i < (r); ++i)
#define R(i, l, r) for (int i = (r) - 1; i >= (l); --i)
#define ALL(x) (x).begin(), (x).end()
#define mem(a, x) memset((a), (x), sizeof(a))
#define sz(a) (int)((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
// clang-format on
#pragma endregion

// Coding Space

// vars

// funcs

using Fp = Modint1000000007;

Fp ml(ll n) {
    return (Fp(4) / Fp(3)) * Fp(4).pow(n - 1) - Fp(4) / Fp(3);
}

void main_() {
    Str S, T;
    cin >> S >> T;
    int k;
    cin >> k;
    if (sz(S) < sz(T)) S = Str(sz(T) - sz(S), '0') + S;
    else T = Str(sz(S) - sz(T), '0') + T;
    int N = sz(S);
    L(i, 0, N) {
        if (S[i] == T[i]) S[i] = T[i] = '0';
        else S[i] = '0', T[i] = '1';
    }
    reverse(ALL(S));
    reverse(ALL(T));
    while (not S.empty()) {
        if (S.back() == '0' and T.back() == '0') {
            S.pop_back();
            T.pop_back();
        } else {
            break;
        }
    }
    reverse(ALL(S));
    reverse(ALL(T));
    N = sz(S);
    if (N == 0) {
        cout << ml(k) << endl;
    } else {
        int c = 0, f = 0;
        R(i, 0, N) {
            if (T[i] == '0') ++c;
            else {
                f = i;
                break;
            }
        }
        if (k > c / 2 + 1) {
            cout << -1 << endl;
            return;
        }

        cerr << S << ' ' << T << endl;
        Fp base = 0;
        if (N % 2 == 1) {
            S = '0' + S;
            T = '0' + T;
            ++f;
            ++N;
        }
        for (int i = 0; i < N; i += 2) {
            Fp v = ml(N / 2 - i / 2);
            if (T[i] == '0' and T[i + 1] == '1') base += v + 1;
            else if (T[i] == '1' and T[i + 1] == '1') base += Fp(2) * v + 2;
            else if (T[i] == '1') base += Fp(3) * v + 3;
        }
        Fp iad = 0;
        L(i, 0, k - 1) {
            iad += ml(i + 2);
        }
        cout << base + iad << endl;
    }
}

set<pair<int, int>> s;
map<int, int> c;

void main_2() {
    int n = 0;
    int test = 100000;
    while (test--) {
        ++c[n];
        L(i, 0, 30) {
            if (s.find(minmax(n, n xor (1 << i))) == s.end()) {
                s.insert(minmax(n, n xor (1 << i)));
                n = n xor (1 << i);
                break;
            }
        }
    }
    for (auto [a, b] : c) cout << bitset<11>(a) << ' ' << b << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if constexpr (IS_MULTITEST == 0) {
        main_2();
        // main_();
    } else {
        // multitest (cf-style)
        int T;
        cin >> T;
        while (T--) {
            main_();
            cout << flush;
        }
    }
}

answer.code:10:10: fatal error: angel/math/modint.hpp: No such file or directory
   10 | #include "angel/math/modint.hpp"
      |          ^~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.