#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

template <int mod>
struct static_modint {
    using mint = static_modint;
    int x;

    static_modint() : x(0) {}
    static_modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    mint& operator+=(const mint& rhs) {
        if ((x += rhs.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        if ((x += mod - rhs.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        x = (int) (1LL * x * rhs.x % mod);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint pow(long long n) const {
        mint _x = *this, r = 1;
        while (n) {
            if (n & 1) r *= _x;
            _x *= _x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const { return pow(mod - 2); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs.x == rhs.x;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs.x != rhs.x;
    }

    friend ostream &operator<<(ostream &os, const mint &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, mint &a) {
        int64_t t; is >> t;
        a = static_modint<mod>(t);
        return (is);
    }
};

const unsigned int mod = 1e9+7;
using modint = static_modint<mod>;
modint mod_pow(ll n, ll x) { return modint(n).pow(x); }
modint mod_pow(modint n, ll x) { return n.pow(x); }

template<class T>
struct Mat{
    vector<vector<T>> A;
    Mat(){}
    Mat(size_t n,size_t m):A(n,vector<T>(m,0)){}
    Mat(size_t n):A(n,vector<T>(n,0)){};
    size_t height() const{
        return A.size();
    }
    size_t width() const{
        return A[0].size();
    }
    inline const vector<T> &operator[](int k) const{
        return A.at(k);
    }
    inline vector<T> &operator[](int k){
        return A.at(k);
    }
    static Mat I(size_t n){
        Mat mat(n);
        for(int i=0;i<n;i++){
            mat[i][i]=1;
        }
        return mat;
    }
    Mat &operator+=(const Mat &B){
        size_t n=height(),m=width();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                (*this)[i][j]=(*this)[i][j]+B[i][j];
            }
        }
        return (*this);
    }
    Mat &operator-=(const Mat &B){
        size_t n=height(),m=width();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                (*this)[i][j]=(*this)[i][j]-B[i][j];
            }
        }
        return (*this);
    }
    Mat &operator*=(const Mat &B){
        int n=height(),m=B.width(),p=width();
        assert(p==B.height());
        vector<vector<T>> C(n,vector<T>(m,0));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<p;k++){
                    C[i][j] += (*this)[i][k]*B[k][j];
                }
            }
        }
        A.swap(C);
        return (*this);
    }
    Mat &operator^=(ll k){
        Mat B=Mat::I(height());
        while(k){
            if(k%2)B*=(*this);
            (*this)*=(*this);
            k>>=1LL;
        }
        A.swap(B.A);
        return (*this);
    }
    Mat operator+(const Mat &B) const{
        return (Mat(*this)+=B);
    }
    Mat operator-(const Mat &B) const{
        return (Mat(*this)-=B);
    }
    Mat operator*(const Mat &B) const{
        return (Mat(*this)*=B);
    }
    Mat operator^(const Mat &B) const{
        return (Mat(*this)^=B);
    }
};

const int N = 1000100;
modint pcal[N]; // pcal[i] : i番目に0を作るのに必要な操作回数
modint psum[N];

void debug() {
    set<pair<int,int>> st;
    const int n = 1000; // 試行回数の上限
    const int bit = 6; // ビット数(< 30)
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        printf("%03d: ", i);
        cout << bitset<bit>(cur) << endl;
        bool ok = false;
        for (int j = 0; j < bit; ++j) {
            int nxt = cur^(1<<j);
            if (st.find({cur, nxt}) == st.end()) {
                st.insert({cur, nxt});
                st.insert({nxt, cur});
                cur = nxt;
                ok = true;
                break;
            }
        }
        if (!ok) break;
    }
}

modint slv_0(int K) {
    Mat<modint> A = Mat<modint>(3, 3);
    A[0][1] = 3, A[0][2] = 4, A[1][0] = 0, A[1][1] = 4, A[1][2] = 4, A[2][2] = 1;
    Mat<modint> B(3, 1);
    B[2][0] = 1;
    A ^= (K-1);
    return (A*B)[1][0];
}

void slv(int n, vector<bool> &bit, int K) {
    modint res = 0;
    int sum = 0;
    for (int i = n-2; i >= 0; i -= 2) {
        if (!bit[i] and !bit[i+1]) {
            sum += 1;
            continue;
        }
        int id = i/2;
        sum = 0;
        res += psum[id];
        if (bit[i] and !bit[i+1]) {
            res += 1;
        }
        else if (bit[i] and bit[i+1]) {
            res += 1 + psum[id] + 1;
        }
        else {
            res += 1 + psum[id] + 1 + psum[id] + 1;
        }
    }
    if (K > sum + 1) {
        cout << -1 << "\n";
        return;
    }
    res += slv_0(K);
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//    debug();
    for (int i = 1; i < N; ++i) {
        pcal[i] = (pcal[i-1]+1)*3 + 1;
        psum[i] = pcal[i] + psum[i-1];
//        if (i < 10) {
//            cout << pcal[i] << " " << psum[i] << endl;
//        }
    }

    int q; cin >> q;
    while (q--) {
        string s,t; cin >> s >> t;
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        int K; cin >> K;
        int len = max(s.size(), t.size());
        if (len%2) len += 1;
        vector<bool> bit(len);
        bool zero = true;
        for (int i = 0; i < len; ++i) {
            int ss = 0, tt = 0;
            if (i < s.size()) ss = s[i]-'0';
            if (i < t.size()) tt = t[i]-'0';
            ss ^= tt;
            bit[i] = ss;
            if (ss) zero = false;
        }

        if (zero) cout << slv_0(K) << "\n";
        else slv(len, bit, K);
    }
}