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

typedef long long ll;

const int N=1e6+5;
const ll mod=1e9+7;
const ll inv3=333333336;

string s,t;int k;
int xo[N],so[N>>1];
// ll sk[N];
ll ans;
int tim[4]={0,1,3,2};

// void init(int num){
//     ll tad=1;
//     sk[0]=tad;
//     for(int i=1;i<=num;i++){
//         tad=tad*4%mod;
//         sk[i]=(sk[i-1]+tad)%mod;
//     }
// }

ll qpow(ll a,int b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

ll sk(ll k){
    return (qpow(4,k+1)-1+mod)%mod*inv3%mod;
}

void solve(){
    ans=0;
    cin>>s>>t>>k;
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    int n=max(s.size(),t.size());
    for(int i=0;i<n;i++){
        if(i>=s.size())xo[i]=t[i]-'0';
        else if(i>=t.size())xo[i]=s[i]-'0';
        else xo[i]=(s[i]-'0')^(t[i]-'0');
        so[i]=0;
    }
    int m=-1,zr=-1;
    for(int i=0;i<n;i++){
        if(i&1)(so[i>>1]|=(xo[i]<<1));
        else (so[i>>1]|=xo[i]);
        if(so[i>>1]>0){
            m=(i>>1);
            if(zr==-1)zr=(i>>1);
        }
    }
    m++;
    if(m==0){
        cout<<sk(k-1)-1<<"\n";
        return;
    }
    // cout<<k<<" "<<zr<<"\n";
    if(k>zr+1){
        cout<<-1<<"\n";
        return;
    }
    for(int i=0;i<m;i++){
        ans=(ans+sk(i))*tim[so[i]]%mod;
    }
    ans=(ans+sk(k-1)-1+mod)%mod;
    cout<<ans<<"\n";
}

int main(){
    // freopen("wait.in","r",stdin);
    // freopen("wait.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    // init(1e6);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}
/*
1
10011001111000111101010100011110000010100001011111 10011001111000111101010100011110000010100001011111 1000000000
*/