#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;
}
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);
        int cnt=0;
        for(i=0;i<n;++i)if(a[i])++cnt;
        if(!cnt)printf("%d\n",(x[k-1]+M-1)%M);
        else{
            if(k>2)puts("-1");
            else{
                d64 ans=0;
                if(n&1)a[n++]=0;
                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];
                }
                if(k==2){
                    if(a[0]||a[1])ans=-1;
                    else (ans+=4)%M;
                }else ans%=M;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}