#include <bits/stdc++.h>
using namespace std;
#define i64 long long
#define int long long
const i64 mod = 1e9 + 7;
i64 invs;
inline i64 quickpow(i64 a, i64 b)
{
    i64 res = 1ll;
    while (b)
    {
        if (b & 1ll)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1ll;
    }
    return res % mod;
}
inline i64 quickinv(i64 a)
{
    return quickpow(a, mod - 2) % mod;
}
int check(string &a, string &b)
{
    int tag = 0;
    int sz = a.size();
    string c;
    c.resize(sz);
    for (int i = sz - 1; i >= 0; i--)
    {
        if (a[i] - b[i] - tag < 0)
        {
            c[i] = '1', tag = 1;
        }
        else
        {
            c[i] = '0' + a[i] - b[i] - tag;
            tag = 0;
        }
    }
    string d;
    for (int i = 0; i < sz; i += 4)
    {
        int tmp = 0;
        for (int j = i; j < i + 4; j++)
        {
            tmp = (tmp << 1) + (c[j] & 15);
        }
        d.push_back('0' + tmp / 4);
        d.push_back('0' + tmp % 4);
    }
    int ans = 1;
    for (int i = d.size() - 1; i >= 0; i--)
    {
        if (d[i] == '0')
            ans++;
        else
            break;
    }
    if (ans == d.size() + 1)
        ans = 1e8;
    return ans;
}
void solve()
{
    string a, b;
    cin >> a >> b;
    i64 k;
    cin >> k;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int sz = max(a.size(), b.size());
    sz = ((sz + 7) / 8) * 8;
    a.resize(sz, '0');
    b.resize(sz, '0');
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    for (int i = 0; i < sz; i++)
    {
        if (b[i] == '1' && a[i] == '0')
        {
            swap(a, b);
            break;
        }
    }
    string c;
    int cnt = check(a, b);
    if (k > cnt)
    {
        cout << -1 << endl;
        return;
    }
    i64 ans = mod - 1;
    c.resize(sz);
    for (int i = 0; i < sz; i++)
    {
        c[i] = '0' + ((a[i] - '0') ^ (b[i] - '0'));
    }
    reverse(c.begin(), c.end());
    for (int i = 0; i < c.size(); i += 2)
    {
        i64 p = (((quickpow(4, i / 2 + 1) + mod - 1) % mod) * invs) % mod;
        if (c[i] == '0')
        {
            if (c[i + 1] == '0')
                ans = ans;
            else
                ans = (ans + (3ll * p) % mod) % mod;
        }
        else
        {
            if (c[i + 1] == '0')
                ans = (ans + p) % mod;
            else
                ans = (ans + (p * 2) % mod) % mod;
        }
    }
    // cout << ans << endl;
    i64 delta = ((quickpow(4, k) + mod - 1ll) % mod) * invs % mod;
    ans = (ans + delta) % mod;
    cout << ans << endl;
}
signed main()
{
    invs = quickinv(3);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
}