#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
//inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
int turn[4] = {0,1,3,2};
const int N = 1e6, p = 1e9+7;
int POW4[N+10], Sum[N+10];
ll quick_pow(ll a,int b) 
{
    a%=p;
    ll ans=1;
    for(;b;b>>=1)
    {
     if(b&1) ans=ans*a%p;
     a=a*a%p;
    }
    return ans;
}
ll inv(ll x) 
{
    return quick_pow(x,p-2);
}
void solve()
{
    string s,t;
    int k;
    cin>>s>>t>>k;
    int n = s.size(), m = t.size();
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    int MAX = max(n,m);
    MAX += (MAX&1);
    vector<int> S(MAX),T(MAX),X(MAX/2);
    for(int i=0;i<n;++i) S[i] = s[i]-'0';
    for(int i=0;i<m;++i) T[i] = t[i]-'0';
    for(int i=0;i<MAX;i+=2) X[i/2] = turn[(S[i]^T[i])+(S[i+1]^T[i+1])*2];
    if(*max_element(X.begin(),X.end()) == 0)
    {
        int inv3 = inv(3);
        ll res = (ll)(quick_pow(4,k) - 4 + p)*inv(3) % p;
        cout<<res<<'\n';
    }
    else if(X[0] != 0) {cout<<"-1\n";return ;}
    else
    {
        auto cal = [&]()->ll
        {
            ll res = 0;
            for(int i=0;i<MAX/2;++i)
            {
                res += (ll)POW4[i]*X[i];
                if(i) res += X[i] * Sum[i-1];
                res %= p;
            }
            return res;
        };
        cout<< (cal() + (ll)(quick_pow(4,k) - 4 + p)*inv(3)) % p<<'\n';
    }
}
int main()
{
	POW4[0] = 1;
    for(int i=1;i<=(int)1e6;++i)
    {
        POW4[i] = (ll)POW4[i-1] * 4 % p;
    }
    Sum[0] = 1;
    for(int i=1;i<=(int)1e6;++i)
    {
        Sum[i] = ((ll)Sum[i-1] + POW4[i])%p;
    }
    ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}