#include<cstdio>
#include<cstring>
const int N=1000010;
const int mod=1e9+7;
char s[N],t[N],tmp[N];
int max(int x,int y){
	return x>y?x:y;
}
void work(){
	scanf("%s",s),scanf("%s",t);
    int lens=strlen(s),lent=strlen(t);
	int len=max(lens,lent);
    if(len&1)len++;
    for(int i=lens;i<len;i++)s[i]='0';
    for(int i=lent;i<len;i++)t[i]='0';
    for(int i=0;i<lens-i-1;i++){
        char ch=s[i];
        s[i]=s[lens-i-1];
        s[lens-i-1]=ch;
    }
    for(int i=0;i<lent-i-1;i++){
        char ch=t[i];
        t[i]=t[lent-i-1];
        t[lent-i-1]=ch;
    }
    // for(int i=0;i<len;i++)putchar(s[i]);
        // puts("");
	for(int i=0;i<len;i++){
        // tmp[i]=s[len-i-1];
        // putchar(s[i]),putchar(t[i]),puts("");
        if(s[i]==t[i])s[i]='0';
        else s[i]='1';
		// if(s[i]==t[i])t[i]='0';
		// else t[i]='1';
	}
    // for(int i=0;i<len;i++)s[i]=tmp[i];
    // for(int i=0;i<len;i++)putchar(s[i]);
    // puts("");
    int k;
    scanf("%d",&k);
    int ans=0;
    int flag=1;
    for(int i=0;i<len;i++)if(s[i]!='0')flag=0;
	if(k==1){
		for(int i=0,now=1,now1=0;i+1<len;i+=2){
            int x;
            if(s[i]=='0'&&s[i+1]=='0')x=0;
            else if(s[i]=='1'&&s[i+1]=='0')x=1;
            else if(s[i]=='1'&&s[i+1]=='1')x=2;
            else if(s[i]=='0'&&s[i+1]=='1')x=3;
            ans=(ans+1ll*now1*x+x)%mod;
            now=1ll*now*4%mod;
            now1=(now+now1)%mod;
            // printf("%d %d %d %d %d\n",i,now,now1,ans,x);
        }
        printf("%d\n",ans);
	}
    else if(flag){
        k--;
        int now=0,now1=1;
        for(int i=1;i<=k;i++){
            now1=1ll*now1*4%mod;
            now=(now+now1)%mod;
        }
        printf("%d\n",now);
    }
    else {
        int cnt=0;
        for(int i=0,now=1,now1=0;i+1<len;i+=2){
            int x;
            if(s[i]=='0'&&s[i+1]=='0')x=0;
            else if(s[i]=='1'&&s[i+1]=='0')x=1;
            else if(s[i]=='1'&&s[i+1]=='1')x=2;
            else if(s[i]=='0'&&s[i+1]=='1')x=3;
            ans=(ans+1ll*now1*x+x)%mod;
            now=1ll*now*4%mod;
            now1=(now+now1)%mod;
        }
        int ggg=0;
        for(int i=0;i<len;i+=2){
            if(s[i]=='0'&&s[i+1]=='0')ggg++;
            else break;
        }
        k--;
        if(k>ggg)puts("-1");
        else {
            int now=0,now1=1;
            for(int i=1;i<=k;i++){
                now1=1ll*now1*4%mod;
                now=(now+now1)%mod;
            }
            ans=(ans+now)%mod;
            printf("%d\n",ans);
        }
        // printf("%d %d %d %d %d\n",i,now,now1,ans,x);
    }
    for(int i=0;i<len+5;i++)s[i]=t[i]=0;
}
int main(){
    // freopen("a.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)work();
    return 0;
}