#include <bits/stdc++.h>

#define Max 2000005

using namespace std;

const int mod=1e9+7;

int T,k,N,s[Max],t[Max];
char S[Max];

inline int qpow(int x,int y){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return ans;
}

inline bool check0(){
    for(int i=N;i>=1;i--){
        if(t[i]==1)return false;
    }
    return true;
}

inline bool check1(){
    int cnt=0;
    for(int i=N;i>=1;i--){
        if(t[i]==1){
            if(i%2==0)return false;
            cnt++;
        }
    }
    return (cnt==1);
}

inline int calc1(){
    for(int i=N;i>=1;i--){
        if(t[i]==1){
            return (i-1)/2;
        }
    }
    return 0;
}

inline int calc(int k){
    if(!k)return 0;
    return (1ll*(qpow(4,k)-1+mod)*qpow(3,mod-2)%mod-1+mod)%mod;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",S+1);
        int n=strlen(S+1);
        for(int i=1;i<=n;i++)s[n-i+1]=S[i]-'0';
        scanf("%s",S+1);
        scanf("%d",&k);
        int m=strlen(S+1);
        for(int i=1;i<=m;i++)t[m-i+1]=S[i]-'0';
        N=max(n,m);
        for(int i=1;i<=N;i++)t[i]=s[i]^t[i];
        // for(int i=N;i>=1;i--)cout<<t[i];cout<<endl;
        if(check0()){
            printf("%d\n",(1ll*(qpow(4,k)-1+mod)*qpow(3,mod-2)%mod-1+mod)%mod);
        }else if(k==1){
            int ans=0;
            for(int i=N;i>=1;i--){
                if(t[i]==1){
                    if(i&1){
                        ans=(ans+calc(i/2+1)+1)%mod;
                    }else{
                        ans=(ans+2ll*calc(i/2)%mod+2)%mod;
                        t[i-1]^=1;
                    }
                }
            }
            printf("%d\n",ans);
        }else if(k==2){
            if(check1()){
                int p=calc1();
                printf("%d\n",(2ll*calc(p+1)+1)%mod);
            }else{
                puts("-1");
            }
        }else{
            puts("-1");
        }

        for(int i=1;i<=N;i++)s[i]=t[i]=0;
    }
    return 0;
}