#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
const int N=1e6;
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
int ksm(ll x,int tp,int s=1){
    for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
    return s;
}
int f[N+5];
void prep(){
    f[1]=4;
    for(int i=2;i<=N;i++)
        f[i]=(3ll*f[i-1]+4)%mod;
}
int n,m,k;
char s[N+5],t[N+5];
int a[N+5];
bool chk0(){
    for(int i=1;i<=n;i++)
        if(a[i]>0) return 0;
    return 1;
}
void solve(){
    scanf("%s %s %d",s+1,t+1,&k);
    n=strlen(s+1); m=strlen(t+1);
    reverse(s+1,s+1+n);
    reverse(t+1,t+1+m);
    for(int i=n+1;i<=max(n,m)+1;i++) s[i]='0';
    for(int i=m+1;i<=max(n,m)+1;i++) t[i]='0';
    // printf("%s\n%s\n",s+1,t+1);
    n=max(n,m);
    for(int i=1;i*2-1<=n;i++){
        a[i]=(s[i<<1]-'0')^(t[i<<1]-'0');
        a[i]<<=1;
        a[i]|=(s[i*2-1]-'0')^(t[i*2-1]-'0');
        // printf("%d",a[i]);
    }
    // puts("");
    n=n+1>>1;
    if(chk0()){
        printf("%d\n",sub(ksm(3,k),(2*k+1)%mod));
        return;
    }
    int ans=0,l=0;
    while(a[l+1]==0) l++;
    for(int i=n;i;i--)
        if(a[i]>0){
            ans=add(ans,f[i-1]+1);
            if(a[i]==2||a[i]==3) ans=add(ans,f[i-1]+1);
            if(a[i]==2) ans=add(ans,f[i-1]+1);
        }
    if(l<k-1) puts("-1");
    else printf("%d\n",add(ans,f[k-1]));
}
int main(){
    prep();
    int t; scanf("%d",&t);
    while(t--) solve();
}