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

typedef long long ll;

const int N=1e6+5,K=1e9+5;
const ll mod=1e9+7;

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

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;
    }
}

void solve(){
    ans=0;
    cin>>s>>t>>k;
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    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>>1]=0;
    }
    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]-sk[0]<<"\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)%mod;
    }
    ans=(ans+sk[k-1]-sk[0])%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(1e9);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}
/*
1
 110011001 
1100001111
2
*/
/*
1010010110
*/

/tmp/ccD0rNqz.o: in function `solve()':
answer.code:(.text+0xb9): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0xdf): relocation truncated to fit: R_X86_64_PC32 against symbol `t[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0xee): relocation truncated to fit: R_X86_64_PC32 against symbol `k' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0xfd): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0x104): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0x13d): relocation truncated to fit: R_X86_64_PC32 against symbol `t[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0x144): relocation truncated to fit: R_X86_64_PC32 against symbol `t[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0x17d): relocation truncated to fit: R_X86_64_PC32 against symbol `t[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0x184): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0x1a6): relocation truncated to fit: R_X86_64_PC32 against symbol `s[abi:cxx11]' defined in .bss section in /tmp/ccD0rNqz.o
answer.code:(.text+0x1af): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status