#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int mod=1e9+7;
constexpr int N = 2e6 + 10, inf = 1e18;
int a[N];
int por(int x,int y){
    int cnt=1,sum=x;
    while(y){
        if(y&1) cnt=cnt*sum%mod;
        sum=sum*sum%mod;
        y>>=1;
    }
    return cnt;
}
void solve() {
    int k;
    string s, t, ob;
    cin >> s >> t;
    cin>>k;
    ob.resize(max(s.size(), t.size()));
    int idx1 = s.size() - 1, idx2 = t.size() - 1;
    for(int i = ob.size() - 1; i >= 0; i --){
        ob[i] = 0;
        if(idx1 >= 0)
            ob[i] ^= s[idx1 --] - '0';
        if(idx2 >= 0)
            ob[i] ^= t[idx2 --] - '0';
        ob[i] += '0';
    }
    if(ob.size()%2) ob="0"+ob;
    reverse(ob.begin(),ob.end());
    int x=ob.size()-1;
    while(ob.size()>2&&ob[x]=='0'&&ob[x-1]=='0'){
        ob.pop_back();
        ob.pop_back();
        x-=2;
    }
    if(ob=="00"){
        int ans=(4*(por(4,k-1)-1)%mod)*por(3,mod-2)%mod;
        cout<<ans<<endl;
        return ;
    }
    int cnt=ob.size()/2-1;
    int sum=(4*(por(4,cnt)-1)%mod)*por(3,mod-2)%mod,ans=sum;
    for(int i=ob.size()-1;i>=0;i-=2){
        if(ob[i]=='0'&&ob[i-1]=='1') ans=ans+1;
        if(ob[i]=='1'&&ob[i-1]=='1') ans=(ans+1+sum+1)%mod;
        if(ob[i]=='1'&&ob[i-1]=='0') ans=(ans+1+sum+1+sum+1)%mod;
        if(cnt>0) sum=((sum-por(4,cnt))%mod+mod)%mod;
        cnt--;
    }
    int num=0;
    for(int i=0;i<ob.size();i++){
        if(ob[i]=='0') num++;
        else break;
    }
    if(num%2) num--;
//    cout<<num<<endl;
    if(k==1){
        cout<<ans<<endl;
        return ;
    }
    if(k>(num/2)+1){
        cout<<-1<<endl;
    }
    else{
        ans=(ans+(4*(por(4,k-1)-1)%mod)*por(3,mod-2)%mod)%mod;
        cout<<ans<<endl;
    }
}

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