#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll ,ll > PII;
const ll N=1e6+10;
const ll M=1e7+10;
const ll mod=1e9+7;
ll a[N];
ll cnt=0;
ll b[M];
ll bb[M];
ll po(ll x,ll y){
    ll ans=1;
    ll base=x;
    while(y){
        if(y%2==1){
            ans*=base;
            ans%=mod;
        }
        base*=base;
        base%=mod;
        y/=2;
    }
    return ans%mod;
}
ll js(ll x){
    return 4*(po(4,x)+mod-1)%mod*po(3,mod-2)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t;
    cin>>t;
    b[0]=1;
    bb[0]=0;
    for(ll i=1;i<M;i++){
        b[i]=b[i-1]*4%mod;
        bb[i]=(bb[i-1]+b[i])%mod;
        // bb[i]%=mod;
        // cout<<"bb["<<i<<"]="<<bb[i]<<endl;
    }
    while(t--){
        string s,t;
        cin>>s>>t;
        ll k;
        cin>>k;
        cnt=1;
        ll lens=s.length()-1,lent=t.length()-1;
        if(lens>lent){
            for(ll i=0;i<=lent;i++){
                a[cnt++]=(s[lens-i]-'0')^(t[lent-i]-'0');
            }
            for(ll i=lens-lent-1;i>=0;i--){
                a[cnt++]=(s[i]-'0');
            }
            cnt--;
        }
        else{
            for(ll i=0;i<=lens;i++){
                a[cnt++]=(s[lens-i]-'0')^(t[lent-i]-'0');
            }
            for(ll i=lent-lens-1;i>=0;i--){
                a[cnt++]=(t[i]-'0');
            }
            cnt--;
        }
        // ll f=0;
        while(cnt>=0 && a[cnt]==0) cnt--;
        if(cnt<0){
            cout<<js(k-1)<<endl;
            continue;
        }
        ll ans=0;
        ll dep=cnt/2-1;
        // ans+=bb[dep];
        ll kk=0;
        // cout<<cnt<<endl;
        // for(ll i=1;i<=cnt;i++){
        //     cout<<a[i];
        // }
        // cout<<endl;
        for(ll i=1;i<=cnt;i+=2){
            if(a[i]==0 && a[i+1]==0) kk++;
            else break;
        }
        ll sec=kk+1;
        // cout<<ans<<endl;
        // cout<<kk<<endl;
        while(cnt){
            if(a[cnt]==1 && a[cnt-1]==1){
                ans+=bb[dep]*2+2;
                ans%=mod;
                dep--;
                cnt-=2;
            }
            else if(a[cnt]==0 && a[cnt-1]==1){
                ans+=bb[dep]+1;
                ans%=mod;
                dep--;
                cnt-=2;
            }
            else if(a[cnt]==0 && a[cnt-1]==0){
                dep--;
                cnt-=2;
            }
            else{
                ans+=bb[dep]*3+3;
                ans%=mod;
                dep--;
                cnt-=2;
            }
            // cout<<ans<<endl;
        }
        if(k>sec) cout<<-1<<endl;
        else{
            // cout<<ans<<endl;
            ans+=js(k-1);
            ans%=mod;
            cout<<ans<<endl;
        }
        
    }
    return 0;
}