#include<stdio.h>
#include<string.h>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int word;
typedef unsigned short hword;
typedef unsigned char byte;
const word mod=109+7;
word f[1<<20];
struct READ{
	char c,w;
	inline READ(){
		for(word i=1;i<(1<<20);++i)
			f[i]=4ull*(f[i-1]+1)%mod;
		c=getchar();}
	template<typename type>
	inline READ& operator>>(type &num){
		for(w=1;'0'>c||c>'9';c=getchar())
			w=c=='-'? -1:1;
		for(num=0;'0'<=c&&c<='9';c=getchar())
			num=num*10+(c-'0');
		return num*=w,*this;
	}
	inline word operator>>(char b[]){
		while('0'>c||c>'1') c=getchar();
		word n=0;
		for(;'0'<=c&&c<='1';c=getchar())
			b[n++]=c-'0';
		for(word i=0;i<n-i;++i)
			std::swap(b[i],b[n-i-1]);
		return n;
	}
}cin;
word case_,k,n,m;
char s[1<<20],t[1<<20];
int main(){
	for(cin>>case_;case_;--case_){
		n=cin>>s,m=cin>>t,cin>>k,--k;
		for(;n<m;++n) s[n]=0;
		for(;m<n;++m) t[m]=0;
		for(word i=0;i<n;++i)
			s[i]^=t[i];
		if(n&1) s[n++]=0;
		for(m=0,n>>=1;m<n&&!(s[m<<1]||s[m<<1|1]);++m);
		if(m==n) printf("%u\n",f[k]);
		else if(m<k) puts("-1");
		else{
			ull ans=f[k];
			for(;m<n;++m){
				const char get=(s[m<<1|1]<<1)|s[m<<1];
				if(get==1) ans+=f[m]+1;
				else if(get==3) ans+=2ull*(f[m]+1);
				else if(get==2) ans+=3ull*(f[m]+1);
			}
			printf("%llu\n",ans%mod);
		}
	}
	return 0;
}