#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fio std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
template<typename T>void read(T &x){
    x=0;
    char c=getchar();
    T ret=0;
    while(!isdigit(c))ret|=!(c^'-'),c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(ret)x=(~x)+1;
}
template<typename T,typename ...Args>
void read(T &x,Args &...xs){
    read(x);read(xs...);
}
template<typename T>void print(T x){
    if(x<0)putchar('-'),x=(~x)+1;
    if(x>9)print(x/10);
    putchar((x-x/10*10)^48);
}
template<typename T>void wr1(T x){
    print(x);putchar(' ');
}
template<typename T>void wr2(T x){
    print(x);putchar('\n');
}
const ll P=1e9+7,N=1e6+10;
int T,k;
ll sum[N],S[]={0,1,3,2},inv3;
ll qpow(ll x,ll y){
    ll ret=1;
    for(;y;y>>=1,x=x*x%P){
        if(y&1)ret=ret*x%P;
    }
    return ret;
}
bitset<N>s,t;
int main(){
    fio;
    for(ll i=2,j=4;i<=1e6;++i,j=j*4%P){
        sum[i]=(sum[i-1]+j)%P;
    }
    inv3=qpow(3,P-2);
    cin>>T;
    while(T--){
        string ss,tt;
        cin>>ss>>tt>>k;
        reverse(ss.begin(),ss.end());
        reverse(tt.begin(),tt.end());
        int len=max(ss.length(),tt.length());
        for(int i=0;i<len;++i){
            s[i]=t[i]=0;
        }
        for(unsigned int i=0;i<ss.length();++i){
            s[i]=ss[i]-'0';
        }
        for(unsigned int i=0;i<tt.length();++i){
            t[i]=tt[i]-'0';
        }
        int x=0,mx1=0;
        bool flg=0;
        for(int i=0;i<len;++i){
            t[i]=s[i]^t[i];
            if(t[i]){
                mx1=i;
                if(!flg)flg=1,x=i;
            }
        }
        if(!mx1&&!t[0]){
            wr2(((qpow(4,k)-1+P)%P*inv3-1+P)%P);
            continue;
        }
        if(k>x/2+1){
            wr2(-1);
        }
        else{
            int pos=0;
            ll ans=sum[k];
            while(pos<=mx1){
                int now=t[pos]*1+t[pos+1]*2;
                ans=(ans+S[now]*(sum[pos/2+1]+1)%P)%P;
                t[pos]=0;
                t[pos+1]=0;
                pos+=2;
            }
            wr2(ans);
        }
    }
    return 0;
}