#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<bitset>
#include<cstring>
#include<queue>
#define fst first
#define sec second
using namespace std;
using ll=long long;
typedef pair<int,int>pii;
const int N=1e6+10;
map<string,int>mp;
const ll mod=1e9+7;
ll pw[N],pre[N];
void init(int n){
    pw[0]=1;
    pre[0]=0;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*4%mod;
    for(int i=1;i<=n;i++)pre[i]=(pre[i-1]+pw[i])%mod;
}
void Silverwolf(){
    string s,t;
    int k;
    cin>>s>>t>>k;
    int f=0;
    if(s.length()<t.length())swap(s,t),f=1;
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    while(t.length()<s.length())t.push_back('0');
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    if(f)swap(s,t);
    //确保位数相等
    int n=s.length();
    for(int i=0;i<n;i++){
        s[i]=(s[i]-'0')^(t[i]-'0')+'0';
    }
    //cout<<s<<'\n';
    
    int cnt=0;
    ll ans=0;
    //算出第一次从0->s的贡献
    for(int i=n-1;i>=0;i-=2){
        string tmp="00";
        tmp[1]=s[i];
        if(i-1>=0)tmp[0]=s[i-1];
        //cout<<mp[tmp]<<' '<<s[0]<<' ';
        //cout<<s[0]<<' '<<mp[tmp]<<'\n';
        //cout<<tmp<<'\n';
        ans=(ans+pre[cnt++]*mp[tmp]%mod+mp[tmp])%mod;
        //cout<<ans<<'\n';
    }
    int flag=0;
    int flag2=0;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='1'){
            break;
            flag2=1;
        }
        flag++;
    }
    if(!flag2)flag=1e9+7;
    k--;
    if(flag<k)return cout<<-1<<'\n',void();
    ans=(ans+pre[k])%mod;
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    mp["00"]=0;
    mp["01"]=1;
    mp["11"]=2;
    mp["10"]=3;
    init(1e6);
    int T;cin>>T;while(T--)
    Silverwolf();
    //愿艾利欧三度为你窥见，令你的生命永不停歇，骇入永远成功，游戏永远胜利。
    //游戏就只是为了游戏，仅此而已
    //acm这种东西，三两下搞定就好啦
    return 0;
}