# include <bits/stdc++.h>

int main() {
  using namespace std;
  constexpr int P(1000000007);
  constexpr int I(333333336);
  constexpr int W[]{ 0, 1, 3, 2 };
  static_assert(3 * I % P == 1);
  auto const pow = [] (int a, int n) {
    int ans(1);
    while (n) {
      ans = n & 1 ? 1ll * ans * a % P : ans;
      n >>= 1, a = 1ll * a * a % P;
    }
    return ans;
  };
  vector<int> c(1, 1);
  c.reserve(1000000);
  while (c.size() < c.capacity())
    c.push_back((4ll * c.back() + 1) % P);
  int t;
  cin >> t;
  for (int i(1); i <= t; ++i) {
    string s, t;
    int k;
    cin >> s >> t >> k;
    if (s == t)
      cout << (1ll * (pow(4, k) - 1) * I % P - 1 + P) % P << endl;
    else {
      reverse(s.begin(), s.end());
      reverse(t.begin(), t.end());
      if (s.size() % 2) s += '0';
      if (t.size() % 2) t += '0';
      vector<int> x(max(s.size() / 2, t.size() / 2), 0);
      for (size_t j(0); j != s.size(); j += 2)
        x[j >> 1] ^= (s[j] - '0') | (s[j + 1] - '0') << 1;
      for (size_t j(0); j != t.size(); j += 2)
        x[j >> 1] ^= (t[j] - '0') | (t[j + 1] - '0') << 1;
      while (!x.back()) x.pop_back();
      int ans(0);
      for (size_t j(0); j != x.size(); ++j)
        ans = (ans + 1ll * W[x[j]] * c[j]) % P;
      if (k == 1)
        cout << ans << endl;
      else if (k == 2 && x.size() > 1 && count(x.begin(), x.end(), 0) == x.size() - 1)
        cout << (ans + c[x.size() - 1] - 1ll + P) % P << endl;
      else cout << -1 << endl;
    }
  }
}