#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;
bitset<N>s,t;
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;
}
int getlen(bitset<N>a){
    int pos=0;
    size_t nex=a._Find_first();
    while(nex!=a.size()){
        pos=nex;
        nex=a._Find_next(nex);
    }
    return pos;
}
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--){
        cin>>s>>t>>k;
        int len=max(getlen(s),getlen(t));
        for(int i=0;i<=len;++i){
            t[i]=t[i]^s[i];
        }
        len=getlen(t);
        if(!len){
            wr2(((qpow(4,k)-1+P)%P*inv3-1+P)%P);
            continue;
        }
        int x=t._Find_first();
        if(k>x/2+1){
            wr2(-1);
        }
        else{
            int pos=0;
            ll ans=sum[k];
            while(pos<=len){
                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;
}