#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
const ll mod=1e9+7;
void solve(){
    int cnt=0;
    string st,ed;
    cin>>st>>ed;
    int k;
    cin>>k;
    int sz_s=st.size(),sz_e=ed.size();
    string ko;
    for(int i=0;i<abs(sz_s-sz_e);i++)   ko.push_back('0');
    if(sz_s>sz_e)   ed=ko+ed;
    else st=ko+st;
    sz_s=max(sz_s,sz_e);
    int le=-1;
    for(int i=sz_s-1;i>=0;i--){
        if(st[i]=='1') ed[i]=(ed[i]=='1'?'0':'1');
        if(ed[i]!='0')  le=sz_s-1-i;  
    }
    if(le!=-1&&k>2){
        cout<<-1<<'\n';
        return ;
    }
    if(le==-1){
        ll ans=1;
        for(int i=1;i<=k-1;i++){
            ans=(ans*4%mod+1)%mod;
        }
        cout<<((ans-1)%mod+1)%mod<<'\n';
        return ;
    }  
    if(ed.size()%2!=0)  ed='0'+ed;
    int sz=ed.size();
    ll sum=0,op=1;ll ge=0;
    bool flag=false;
    for(int i=sz-1;i>=0;i-=2){
        if(ed[i]=='0'&&ed[i-1]=='0');
        else{
            if(!flag){flag=true;ge=op-1;}
            if(ed[i]=='0'&&ed[i-1]=='1')  sum=(sum+op*3%mod)%mod;
            else if(ed[i]=='1'&&ed[i-1]=='1') sum=(sum+op*2%mod)%mod;
            else if(ed[i]=='1'&&ed[i-1]=='0') sum=(sum+op*1%mod)%mod;
        }
        op=(op*4+1)%mod;
    }
    if(k==1)    cout<<sum<<'\n';
    else{
        if(ge==0)   cout<<-1<<'\n';
        else cout<<(sum+ge)%mod<<'\n';
    }
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int _;
    cin>>_;
    while(_--) solve();
    return 0;
}