#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 > 0) {
    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';
    vector<char> tmp(M);
    for(int i = 0; i < M; i++) {
      if(i < n) tmp[M - 1 - i] = s1[n - 1 - i];
      else tmp[M - 1 - i] = '0';
      //s1[M - 1 - i] = 
    }
    for(int i = 0; i < M; i++) s1[i] = tmp[i];
    //reverse(s1, s1 + m);
  } else if(n > m) {
    vector<char> tmp(M);
    for(int i = 0; i < M; i++) {
      if(i < m) tmp[M - 1 - i] = s2[m - 1 - i];
      else tmp[M - 1 - i] = '0';
    }
    for(int i = 0; i < M; i++) s2[i] = tmp[i];
    //for(int i = m; i < M; 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(int i = 0; i < M; i++) printf("%d", T[i]);
  //printf("\n");
  //printf("BIT::%d\n", bit);
  //
  int flag1 = T[M - 1], flag2 = 1;
  if(M > 1) flag2 = T[M - 2];
  if(((flag1 || flag2) && k > 1)) {
    printf("-1\n");
    for(int i = 0; i <= M; i++) s1[i] = s2[i] = 0;
    return;
  }
  int f3 = 0;
  int prez = 0;
  while(prez < M && !T[prez]) f3++;
  if(f3 < k*2 - 2) {
    for(int i = 1; i <= M; i++) s1[i] = s2[i] = 0;
    printf("-1\n");
    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) {
      //if(i < M - 1) ans = () % p;
      int now = 0;
      for(int j = 0; j < 2 && (i - j >= 0); j++) {
        now += T[i - j] << j;
      }
      if(i == 0 && k > (M + 1) / 2) {
        printf("-1\n");
        for(int i = 0; i < M; i++) s1[i] = s2[i] = 0;
        return;
      } else {
        //LL res = res = (i == M - 1) ? 0 : mov[now];
        LL res = 0, ret = (base * 4 % p + p - 4) * inv % p;
        if((i < M - 1) || now) ret++;
        res = res + mov[now] * ret % p;
        ///res++;
        res %= p;
        if((i - 2) < 0) res = (res + base * (k - 1) % p) % p;
        ans = (ans + res) % p;
        
      }
      base = base * 4 % p;
     // rb ++;
     // printf("NOW::%d\n", ans);
      //ans = (ans + base);
    }
    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();
  }
}