#include<cstdio>
typedef long long d64;
const d64 M=1000000007;
int T,n,m,i,k;
d64 x[1000086];
bool A[1000086],B[1000086],*a,*b;
int read(bool *s){
    char c;
    while(c=getchar(),c!='0'&&c!='1');
    int r=0;
    while(c=='0'||c=='1')s[r++]=c-'0',c=getchar();
    return r;
}
void swap(bool &a,bool &b){
    bool c=a;a=b;b=c;
}
d64 pow(d64 u,d64 d){
    if(!u)return 1;
    d64 r=pow(u>>1,d);
    r*=r;
    if(u&1)(r%=M)*=d;
    return r%M;
}
int gans(){
    int cnt=0;
    for(i=0;i<n;++i)if(a[i])++cnt;
    if(!cnt)return ((pow(k,4)+M-1)*pow(M-2,3)+M-1)%M;
    d64 ans=0;
    if(n&1)++n;
    for(i=0;i+i<n;++i){
        int d=0;
        if(a[i+i+1]){
            if(!a[i+i])++d;
            d+=2;
        }else if(a[i+i])++d;
        ans+=d*x[i];
    }
    bool B=1;
    for(i=0;i<k-1;++i)if(a[i+i]||a[i+i+1])return -1;
    return (ans+x[k-1]+M-1)%M;
}
int main(){
    x[0]=1;
    for(i=0;i<=1000000;++i)x[i+1]=(4*x[i]+1)%M;
    scanf("%d",&T);
    while(T--){
        a=A;b=B;
        n=read(a);
        m=read(b);
        for(i=0;i+i<n;++i)swap(a[i],a[n-i-1]);
        for(i=0;i+i<m;++i)swap(b[i],b[m-i-1]);
        if(n<m){
            bool *c=a;a=b;b=c;
            i=n;n=m;m=i;
        }
        for(i=0;i<m;++i)a[i]^=b[i];
        scanf("%d",&k);
        printf("%d\n",gans());
        for(i=0;i<n;++i)a[i]=0;
    }
    return 0;
}