#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rept(i, a, ne) for(int i = (a); ~i ; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
#define fi first
#define sec second
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double  LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int>PII;
LL mod=1e9+7;
LL qmi(LL a,LL b)
{
    LL sum=1;
    while(b)
    {
        if(b&1)sum=sum*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return sum;
}
LL getd(LL n)
{
    return (mod+1-qmi(4,n))*qmi(-3+mod,mod-2)%mod;
}
void slove()
{
 
    string s,t;
    cin>>s>>t;
    int k;
    cin>>k;
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    
    int n=s.size(),m=t.size(); 
    if(n>m)
    swap(s,t),swap(n,m);
    rep(i,0,n-1)
    t[i]=(t[i]^s[i])+'0';
    // debug(t);
    
    int num=0;
    rep(i,0,m-1)
    {

        if(t[i]=='0')
        num++;
        else
        break;

    }
    if(num==m)
    {
        LL sum=getd(k)-1;
        sum=(sum+mod)%mod;
        cout<<sum<<endl;
        return ;
    }
    
    if(k>1+num/2)
    {
        cout<<-1<<endl;
        return ;
    }
    s.resize(0);
    int pp=0;
    per(i,m-1,0)
    {
        if(t[i]=='1')
        pp=1;
        if(pp)
        {
            s+=t[i];
        }
    }
    t=s;
    reverse(t.begin(),t.end());
    m=t.size();
    // debug(t);
    if(m%2)
    m++,t+='0';
    // debug(t);
    int p=m/2;
    LL sum=getd(p);
    //  debug(sum);
    int ds=1;
    for(int i=0;i<m;i+=2)
    {
        ds=getd(i/2+1)%mod;
        int s=t[i]-'0'+2*(t[i+1]-'0'); 
        if(i==m-2)
        {
            if(s==1)
                sum+=0;
            else if(s==3)
                sum+=ds;
            else if(s==2)
                sum+=ds*2%mod; 
            continue;
        }
        if(s==0)
            sum+=0;
        else if(s==1)
            sum+=ds;
        else if(s==3)
            sum+=ds*2%mod;
        else 
            sum+=ds*3%mod;
        
        sum%=mod;
    }
    // debug(sum);
    //  debug(getd(k));
    sum+=getd(k)-1;
    sum=(sum+mod)%mod;
    cout<<sum<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
//	cout << fixed << setprecision(9);
    int t=1;
	cin>>t;
    while(t--)
    {
        slove();
    }


    return 0;
}
//#pragma GCC optimize(2)