#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

template <int mod>
class Modint {
    using mint = Modint;
    static_assert(mod > 0, "Modulus must be positive");

   public:
    static constexpr int get_mod() noexcept { return mod; }

    constexpr Modint(long long y = 0) noexcept
        : x(y >= 0 ? y % mod : (y % mod + mod) % mod) {}

    constexpr int value() const noexcept { return x; }

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

    constexpr mint operator-() const noexcept { return mint(-x); }

    constexpr mint operator+(const mint& r) const noexcept {
        return mint(*this) += r;
    }
    constexpr mint operator-(const mint& r) const noexcept {
        return mint(*this) -= r;
    }
    constexpr mint operator*(const mint& r) const noexcept {
        return mint(*this) *= r;
    }
    constexpr mint operator/(const mint& r) const noexcept {
        return mint(*this) /= r;
    }

    constexpr bool operator==(const mint& r) const noexcept { return x == r.x; }
    constexpr bool operator!=(const mint& r) const noexcept { return x != r.x; }

    constexpr mint inv() const noexcept {
        int a = x, b = mod, u = 1, v = 0;
        while (b > 0) {
            int t = a / b;
            std::swap(a -= t * b, b);
            std::swap(u -= t * v, v);
        }
        return mint(u);
    }

    constexpr mint pow(long long n) const noexcept {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend std::ostream& operator<<(std::ostream& os, const mint& r) {
        return os << r.x;
    }

    friend std::istream& operator>>(std::istream& is, mint& r) {
        long long t;
        is >> t;
        r = mint(t);
        return is;
    }

   private:
    int x;
};
template <typename T>
class Matrix {
   public:
    static Matrix concat(const Matrix& A, const Matrix& B) {
        assert(A.m == B.m);
        Matrix C(A.m, A.n + B.n);
        for (int i = 0; i < A.m; ++i) {
            std::copy(A[i].begin(), A[i].end(), C[i].begin());
            std::copy(B[i].begin(), B[i].end(), C[i].begin() + A.n);
        }
        return C;
    }

    Matrix() = default;
    Matrix(int m, int n) : mat(m, std::vector<T>(n)), m(m), n(n) {}
    Matrix(std::initializer_list<std::initializer_list<T>> list) {
        for (auto& l : list) mat.emplace_back(l);
        m = mat.size();
        n = mat[0].size();
    }

    int row() const { return m; }
    int col() const { return n; }

    const std::vector<T>& operator[](int i) const { return mat[i]; }
    std::vector<T>& operator[](int i) { return mat[i]; }

    Matrix& operator+=(const Matrix& rhs) {
        assert(m == rhs.m && n == rhs.n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] += rhs[i][j];
            }
        }
        return *this;
    }

    Matrix& operator-=(const Matrix& rhs) {
        assert(m == rhs.m && n == rhs.n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mat[i][j] -= rhs[i][j];
            }
        }
        return *this;
    }

    Matrix operator+(const Matrix& rhs) const { return Matrix(*this) += rhs; }
    Matrix operator-(const Matrix& rhs) const { return Matrix(*this) -= rhs; }

    Matrix transpose() const {
        Matrix ret(n, m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                ret[i][j] = mat[j][i];
            }
        }
        return ret;
    }

    Matrix matmul(const Matrix& B) const {
        assert(n == B.m);
        Matrix ret(m, B.n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < B.n; ++j) {
                for (int k = 0; k < n; ++k) {
                    ret[i][j] += mat[i][k] * B[k][j];
                }
            }
        }
        return ret;
    }

    Matrix rref() const {
        Matrix A(*this);
        int pivot = 0;
        for (int j = 0; j < n; ++j) {
            int i = pivot;
            while (i < m && eq(A[i][j], T(0))) ++i;
            if (i == m) continue;

            if (i != pivot) A[i].swap(A[pivot]);

            T p = A[pivot][j];
            for (int l = j; l < n; ++l) A[pivot][l] /= p;

            for (int k = 0; k < m; ++k) {
                if (k == pivot) continue;
                T v = A[k][j];
                for (int l = j; l < n; ++l) {
                    A[k][l] -= A[pivot][l] * v;
                }
            }

            ++pivot;
        }
        return A;
    }

    int rank() const {
        auto A = rref();
        for (int i = 0; i < m; ++i) {
            bool nonzero = false;
            for (int j = 0; j < n; ++j) {
                if (!eq(A[i][j], T(0))) {
                    nonzero = true;
                    break;
                }
            }
            if (!nonzero) return i;
        }
        return m;
    }

    template <typename U,
              typename std::enable_if<std::is_floating_point<U>::value>::type* =
                  nullptr>
    static constexpr bool eq(U a, U b) {
        return std::abs(a - b) < 1e-8;
    }

    template <typename U, typename std::enable_if<!std::is_floating_point<
                              U>::value>::type* = nullptr>
    static constexpr bool eq(U a, U b) {
        return a == b;
    }

   protected:
    std::vector<std::vector<T>> mat;
    int m, n;
};

template <typename T>
class SquareMatrix : public Matrix<T> {
    using Matrix<T>::Matrix;
    using Matrix<T>::eq;
    using Matrix<T>::n;

   public:
    static SquareMatrix I(int n) {
        SquareMatrix ret(n);
        for (int i = 0; i < n; ++i) ret[i][i] = 1;
        return ret;
    }

    SquareMatrix() = default;
    explicit SquareMatrix(int n) : Matrix<T>(n, n) {}
    SquareMatrix(const Matrix<T>& mat) : Matrix<T>(mat) {
        assert(Matrix<T>::m == n);
    }
    SquareMatrix(std::initializer_list<std::initializer_list<T>> list)
        : Matrix<T>(list) {
        assert(Matrix<T>::m == n);
    }

    SquareMatrix pow(long long k) const {
        auto ret = I(n);
        auto A(*this);
        while (k > 0) {
            if (k & 1) ret = ret.matmul(A);
            A = A.matmul(A);
            k >>= 1;
        }
        return ret;
    }

    T det() const {
        SquareMatrix A(*this);
        T ret = 1;
        for (int j = 0; j < n; ++j) {
            int i = j;
            while (i < n && eq(A[i][j], T(0))) ++i;
            if (i == n) return 0;

            if (i != j) {
                A[i].swap(A[j]);
                ret = -ret;
            }

            T p = A[j][j];
            ret *= p;
            for (int l = j; l < n; ++l) A[j][l] /= p;

            for (int k = j + 1; k < n; ++k) {
                T v = A[k][j];
                for (int l = j; l < n; ++l) {
                    A[k][l] -= A[j][l] * v;
                }
            }
        }
        return ret;
    }

    SquareMatrix inv() const {
        assert(!eq(det(), T(0)));
        auto IB = Matrix<T>::concat(*this, I(n)).rref();
        SquareMatrix B(n);
        for (int i = 0; i < n; ++i) {
            std::copy(IB[i].begin() + n, IB[i].end(), B[i].begin());
        }
        return B;
    }
};

using mint = Modint<(int)1e9 + 7>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    const SquareMatrix<mint> mat = {{4, 1}, {0, 1}};

    auto calc = [&](int k) {
        auto res = mat.pow(k - 1);
        return res[0][0] + res[0][1] - 1;
    };

    auto get_index = [&](char d0, char d1) {
        if (d0 == '0' && d1 == '0') return 0;
        if (d0 == '1' && d1 == '0') return 1;
        if (d0 == '1' && d1 == '1') return 2;
        if (d0 == '0' && d1 == '1') return 3;
    };

    int T;
    cin >> T;
    while (T--) {
        string s, t;
        int k;
        cin >> s >> t >> k;
        if (s.size() > t.size()) swap(s, t);
        reverse(all(s));
        reverse(all(t));
        rep(i, 0, s.size()) {
            if (s[i] == '1') {
                t[i] = (t[i] == '0' ? '1' : '0');
            }
        }
        while (t.size() > 0 && t.back() == '0') {
            t.pop_back();
        }
        if (t.size() % 2 == 1) t.push_back('0');
        if (t.empty()) {
            mint ans = calc(k);
            cout << ans << "\n";
        } else {
            mint ans = 0;

            mint sz = 1;
            int num_visit = 1;
            for (int d = 0; d < t.size(); d += 2) {
                if (t.substr(d, 2) == "00") ++num_visit;
                ans += sz * get_index(t[d], t[d + 1]);
                sz = sz * 4 + 1;
            }

            if (k > num_visit) {
                cout << -1 << "\n";
            } else {
                ans += calc(k);
                cout << ans << "\n";
            }
        }
    }
}