#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=0x3f3f3f3f;
const ll infll=0x3f3f3f3f3f3f3f3f;
#define int long long
#define pii pair <int,int>
#define ld long double
#define endl "\n"
const int N=1000050;
string s,t;
string des;
int div4[N];
const int mod=1e9+7;
int qpow(int x,int y){
    int re=1;
    while (y){
        if(y%2==1)re=re*x%mod;
        x=x*x%mod,y/=2;
    }
    return re;
}
int calck(int x){
    int res=(1-qpow(4,x))*qpow((1-4),mod-2);
    return (res+mod-1)%mod;
}
char Xor(char x,char y){
   // cerr <<x<<y<<endl;
    if (x=='1'&&y=='1')return '0';
    else if (x=='0'&&y=='0')return '0';
    return '1';
}
int mp(int x){
    if (x==0)return 0;
    if (x==1)return 1;
    if (x==2)return 3;
    return 2;
}
signed main (){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int tt;
    cin >>tt;
    while (tt--){
        cin >>s>>t;
        int k;
        cin >>k;
        int lens=s.length();
        int lent=t.length();
        if (lens<lent){
            swap(s,t);
            swap (lens,lent);
        }
        des=s;
        
        for (int i=0;i<lent;i++){
            des[lens-1-i]=Xor(des[lens-1-i],t[lent-1-i]);
        }
       // cout <<calck(k)<<endl;
       // cerr <<des<<endl;
        for (int i=des.length()-1,j=0;i>=0;i--,j++){
            div4[j/2]+=(des[i]-'0')*(1+j%2);
        }
        int res=calck(k);
        int cnt=0;
        int flag=0;
        for (int i=0;i<=(lens/2+lens%2-1);i++){
           // cerr <<div4[i]<<endl;
            if (div4[i]==0)cnt++;
            else flag=1;
          //  cerr <<"res:"<<(1+calck(i+1))*mp(div4[i])<<endl;
            res+=(1+calck(i+1))*mp(div4[i]);
            res%=mod;
            div4[i]=0;
        }
        res%=mod;
        if (!flag)cout <<res<<endl;
        else if (cnt+1<k)cout <<-1<<endl;
        else cout <<res<<endl;
        
        //cerr <<endl;
    }
}