#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
const ll mod=1e9+7;
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void solve(){
    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;  
    }
    //cout<<ed<<'\n';
    if(le==-1){
        ll ans=(((qpow(4,k)-4)*qpow(3,mod-2)%mod-1)%mod+mod)%mod;
        cout<<ans<<'\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;
    int cnt=0;
    for(int i=sz-1;i>=0;i-=2){
        if(ed[i]=='0'&&ed[i-1]=='0'){
            if(!flag){
                cnt++;
                if(cnt==k-1)    ge=4*op;
            }  
        }
        else{
            flag=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(cnt<k-1)   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;
}