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

int lowbit(int x) {return x&-x;}

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

//    map<int, int> vis;
//    map<int, vector<int>> cnt;
//
//    int s = 0;
//
//    for(int i=0; i<1000000; i++){
//
//        cnt[s].push_back(i);
//
//        int k = lowbit(~vis[s]);
//        vis[s] ^= k;
//
//        s ^= k;
//
//        vis[s] ^=k;
//
////        cout << i+1 << ": " << __lg(k) + 1 << " => " << bitset<8>(s) << '\n';
//    }
//
//    cout << boolalpha;
//
//    for(auto&[k, v] : cnt){
//        if(k > (1<<10)) break;
//        int N = max(__lg(lowbit(k))/2 + 1, 1);
//        // N == v.size();
//        cout << k << ":\t" << bitset<8>(k) << '\t' << N << " => ";
//        for(auto x : v) cout << x << ' ';
//        cout << '\n';
//    }

    using i64 = long long;
    constexpr int maxn = 1e6 + 5;
    constexpr i64 M = 1e9 + 7;

    auto qpow = [M](i64 x, i64 y) -> i64{
        x %= M; y %= M;
        i64 res = 1;
        while(y){
            if(y&1) res = res*x%M;
            x = x*x%M;
            y >>= 1;
        }
        return res;
    };

    vector<i64> jty(maxn);

    i64 V = 4;
    for(int i=1; i<maxn; i++){
        jty[i] = (jty[i-1] + V) % M;
        V = (V << 2) % M;
    }

    int T; cin >> T;
    while(T--){

        string s, t;
        cin >> s >> t;
        int k; cin >> k;
        i64 ans = 0;


        if(s.size() < t.size()) swap(s, t);

        for(int i=(int)s.size()-1, j=(int)t.size()-1; j >= 0; i--, j--){
            s[i] = (char)((s[i] - '0') ^ (t[j] - '0')) + '0';
        }

        reverse(s.begin(), s.end());

        for(int i=0; i<s.size(); i++){
            if(s[i] != '0'){
                if(k > max(i / 2 + 1, 1)){
                    cout << "-1\n";
                    goto nxt;
                }
            }
            if(i + 1 == s.size()){
                i64 res = (qpow(4, k) + M - 4) % M * qpow(3, M-2) % M;
                cout << res << '\n';
                goto nxt;
            }
        }

        if(s.size() % 2) s.push_back('0');


        for(int i=0; i<s.size(); i+=2){
            i64 a = (s[i] - '0') + (s[i+1] - '0') * 2;

            if(a == 2) a = 3;
            else if(a == 3) a = 2;

            ans = (ans + a * (jty[i>>1] + 1) % M) % M;
        }

        cout << (ans + jty[k-1]) % M << '\n';

        nxt:;
    }


    return 0;
}