//
// Created by Mrlaolu on 2024/7/10.
//

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define x first
#define y second
#define lc root<<1
#define rc root<<1|1
const int N = 1e5+2;
const int MOD = 1e9+7;
using namespace std;
using PII = pair<int,int>;
using i128 = __int128;
#define debug0

int qpow(int x,int n,int p){
    int ans = 1;
    while(n){
        if(n & 1)ans = (ans * x) % p;
        x = (x * x) % p;
        n >>= 1;
    }
    return ans;
}

void solve(){
    string s,t;cin >> s >> t;
    int ans = 0;
    if(s != "0" && t == "0")ans++;
    int k;cin >> k;
    string f;
    if(s.size() > t.size()){
        string k;
        for(int i = 0;i < s.size() - t.size();++i){
            k += '0';
        }
        t = k + t;
    }else if(s.size() < t.size()){
        string k;
        for(int i = 0;i < t.size() - s.size();++i){
            k += '0';
        }
        s = k + s;
    }
    for(int i = 0;i < s.size();++i){
        f += '0' + (s[i] != t[i]);
    }

    if(f.size() & 1)f = '0' + f;
    int len = 0;
    while(len < f.size()){
        if(f[f.size() - 1 - len] != '0')break;
        len++;
    }
//    cout << len << endl;
//    if(len == s.size())len = INT_MAX;
    if(k - 1 > len / 2 && len != f.size()){cout << -1 << endl;return;}
//    vector<int>p = {0,1,3,2};
    int cnt = 0;
//    cout << f << endl;
    for(int i = f.size() - 1;i >= 0;i -= 2){
        if(f[i] == '1' && f[i-1] == '0')ans = (ans + (1ll * qpow(4,cnt,MOD)) % MOD) % MOD;
        if(f[i] == '1' && f[i-1] == '1')ans = (ans + (2ll * qpow(4,cnt,MOD)) % MOD) % MOD;
        if(f[i] == '0' && f[i-1] == '1')ans = (ans + (3ll * qpow(4,cnt,MOD)) % MOD) % MOD;
        ++cnt;
    }

//    cout << ans << endl;
    ans = (ans + 4ll * ((qpow(4,k - 1,MOD) - 1 + MOD) % MOD) % MOD *
            qpow(3,MOD-2,MOD) % MOD ) % MOD;
    cout << ans << endl;

}

#define FILE
#define MULTI

signed main() {


#ifndef ONLINE_JUDGE
#ifdef FILE
    freopen("in.txt", "r",stdin);
    freopen("out.txt", "w",stdout);
#endif
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;

#ifdef MULTI
    cin >> T;
#endif

    while (T--) {
        solve();

    }
    return 0;
}