#include<bits/stdc++.h>
using namespace std;
constexpr int M=5e5+5,mod=1e9+7,inv3=(mod+1)/3;
int n,k,len,a[M],b[M],ans[M],trans[5];
int qpow(int x,int n){
    int s=1; while (n){
        if (n&1) s=1ll*s*x%mod;
        x=1ll*x*x%mod; n>>=1;
    } return s;
}
void solve(){
    string s,t;cin>>s>>t>>k;
    n=max(s.length(),t.length())-1>>1;
    for (int i=0;i<=n;i++) a[i]=b[i]=0;
    len=s.length()-1;for (int i=0;i<=len;i++) (a[len-i>>1]<<=1)|=s[i]-'0';
    len=t.length()-1;for (int i=0;i<=len;i++) (b[len-i>>1]<<=1)|=t[i]-'0';
    for (int i=0;i<=n;i++) a[i]^=b[i];
    int pos=-1,res=1ll*(qpow(4,k)-1)*inv3%mod-1;
    for (int i=0;i<=n;i++)
        if (a[i]) {pos=i;break;}
    if (~pos&&pos+1<k) return puts("-1"),void();
    for (int i=0;i<=n;i++) res=(res+1ll*trans[a[i]]*ans[i])%mod;
    printf("%d\n",res);
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    trans[0]=0;trans[1]=1;trans[3]=2;trans[2]=3;
    for (int i=ans[0]=1;i<M;i++) ans[i]=(ans[i-1]*4ll+1)%mod;
    int T;cin>>T;while (T--) solve();return 0;
}