#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+7;
typedef long long LL;
const int p = 1e9+7;
//int B[N];

char s1[N], s2[N];
LL fst(LL b, int k) {
  LL res = 1;
  while(k) {
    if(k & 1) {
      res = res * b % p;
    }
    k >>= 1;
    b = b * b % p;
  }
  return res;
}

const LL inv = fst(3, p - 2);

int mov[4] = {0, 1, 3, 2};

void solve() {
  int n, m;
  cin >> s1;
  cin >> s2; 
  n = strlen(s1);
  m = strlen(s2);
  int k, bit = 0;
  cin >> k;
  int M = max(n, m); 
  vector<int> T(M + 1);
  if(n < m) {
    for(int i = n; i < m; i++) s1[i] = '0';
    reverse(s1, s1 + m);
  } else if(n > m) {
    for(int i = m; i < n; i++) s2[i] = '0';
    reverse(s2, s2 + n);
  }
  //printf("Power::\n%s\n%s\n", s1, s2);
  //
  for(int i = 0; i < M; i++) {
    if(s1[M - i - 1] != s2[M - i - 1]) {
      T[M - i - 1] = 1;
      bit++;
    }
  }
  //printf("NOW::");
  //for(auto x : T) printf("%d", x);
  //printf("\n");
  //printf("BIT::%d\n", bit);
  //
  if((T[M - 1] & 1 && k > 1)) {
    printf("-1\n");
    for(int i = 0; i <= M; i++) s1[i] = s2[i] = 0;
    return;
  }
  //
  if(!bit) {
    /// k - 1;
    LL Res = ((fst(4, k) + p - 4) % p) * inv % p;
    printf("%lld\n", Res);
    for(int i = 0; i <= M; i++) s1[i] = s2[i] = 0;
    return;
  } else {
    // k == 2 ? ans + ? : ans;
    //
    int rb = 0;
    LL base = 1, ans = 0;
    //printf("Len::%d\n", M);
    for(int i = M - 1; i >= 0; i -= 2) {
      int now = 0;
      for(int j = 0; j < 2 && (i - j > 0); j++) {
        now += T[i - j] << j;
      }
      //printf("NOW::%d\n", now);
      ans = (ans + base * mov[now] % p) % p;
      //printf("MOV::%d\n", now);
      //// upper_bound = (M + 1) / 2;
      if(i == 0) {
        ans++;
        if(k > (M+1)/2) {
          printf("-1\n");
          for(int i = 0; i < M; i++) s1[i] = s2[i] = 0;
          return;
        } else {
          ans = (ans + base * k % p) % p;
        }
      }
      base = base * 4 % p;
    }
    for(int i = 0; i < M; i++) s1[i] = s2[i] = 0;
    printf("%lld\n", ans);
  }
  
  ///clear();
  for(int i = 0; i < M; i++) s1[i] = s2[i] = 0;
}


int main() {
  int T;
  cin >> T;
  while(T--) {
    solve();
  }
}