#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#define x first
#define y second
#define endl '\n'
#define pi acos(-1.0)
using namespace std;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<int, PII> PIII;
typedef pair<PII, char> PIIC;
typedef long long LL;
int dx[] = {1, 0, 0, -1, -1, -1, 1, 1}, dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
int mou[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int N = 1e6 + 10, M = 50 + 10, mod = 1e9+7, INF = 0x3f3f3f3f;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
int n, m,t;
LL f[N];
typedef pair<PII,PII>PPP;
template <typename T>
inline T read()
{
    T x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
LL qmi(LL a, LL b)
{
    LL ans = 1 % mod;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
LL inv(int x)
{
    return qmi(x, mod - 2);
}
LL Random(LL mod)
{
    LL res = INT32_MAX;
    return res * rand() * rand() % mod;
}

void solve()
{
    string s,t;
    cin>>s>>t>>n;
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    while(s.size()<t.size()) s+='0';
    while(s.size()>t.size()) t+='0';
    for(int i=0;i<s.size();i++) s[i]=(s[i]==t[i]?'0':'1');
    while(s.size()>1&&s.back()=='0') s.pop_back();
    if(s.size()%2) s+='0';
    m=0;
    while(m<s.size()&&s[m]=='0') m++;
    //cout<<s<<" ";
    if(s.size()==2&&s=="00");
    else if(m<2*n-2){
        cout<<-1<<endl;
        return;
    }
    LL res=0;
    for(int i=1;i<s.size();i+=2){
        int cnt;
        if(s[i-1]=='0'&&s[i]=='0') cnt=0;
        else if(s[i-1]=='1'&&s[i]=='0') cnt=1;
        else if(s[i-1]=='1'&&s[i]=='1') cnt=2;
        else cnt=3;
        res=(res+f[i/2]*cnt%mod)%mod;
        //res=(res+(qmi(4,i/2+1)-1)*inv(3)%mod*cnt%mod)%mod;
        //cout<<cnt<<" ";
    }
    //cout<<res<<" ";
    //res=(res+(qmi(4,n-1)-1)*4%mod*inv(3)%mod)%mod;
    res=(res+f[n-1]-1)%mod;
    cout<<res<<endl;
}

int main()
{
    //clock_t start,end;//定义clock_t变量
    //start = clock(); 
    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0),cout.precision(10);
    // freopen("in.in","r",stdin);
    // freopen("order.in","w",stdout);
    f[0]=1;
    for(int i=1;i<=N;i++) f[i]=(f[i-1]*4+1)%mod;
    //for(int i=0;i<5;i++) cout<<f[i]<<" ";cout<<endl;
    t = 1; cin >> t;
    while (t--) solve();
    //end = clock();   //结束时间
    //cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}