#include <bits/stdc++.h>

using namespace std ;
const int mod = 1e9 + 7 ;
const int inv3 = 1e9 + 10 ;
const int N = 1e6 + 4 ; 

long long qmi(int a, int b)
{
    long long res = 1 % mod;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * (long long)a % mod;
        b = b >> 1;
    }
    return res;
}

int solve()
{
    if(s.size() == 2 && s == "00") return (qmi(4 , k - 1) + mod - 1) % mod * 4ll % mod * inv3 % mod ;
    int cnt = 0 ;
    while(cnt < s.size() && s[cnt] == '0') cnt ++ ;
    if(cnt < k * 2 - 2) return -1 ;
    long long ans = 0 ;
    for(int i = 1 ; i < s.size() ; i += 2)
    {
        long long t ;
        if(s[i - 1] == '0' && s[i] == '0') t = 0 ;
        else if(s[i - 1] == '1' && s[i] == '0') t = 1 ;
        else if(s[i - 1] == '1' && s[i] == '1') t = 2 ;
        else t = 3 ;

        ans += p[i / 2] * t % mod ;
        if(ans >= mod) ans -= mod ; 
    }

    return (ans + (qmi(4 , k - 1) + mod - 1) % mod * 4ll % mod * inv3 % mod) % mod ;
}

string s , t ;
int k ;
long long p[N] ;

int main()
{
  p[0] = 1 ;
  for(int i = 1 ; i < N ; i ++) p[i] = (p[i - 1] * 4 + 1) % mod ;
  int tc ; cin >> tc ;
  while(tc --)
  {
    cin >> s >> t >> k ;
    reverse(s.begin() , s.end()) ;
    reverse(t.begin() , t.end()) ;
    while(s.size() < t.size()) s += '0' ;
    while (t.size() < s.size()) t += '0' ;
    for(int i = 0 ; i < s.size() ; i ++) s[i] = (s[i] == t[i] ? '0' : '1') ;
    while(s.size() > 1 && s.back() == '0') s.pop_back() ;
    if(s.size() % 2 == 1) s += '0' ;

    cout << solve() << '\n' ;
  }
  return 0 ;
}

answer.code: In function ‘int solve()’:
answer.code:22:8: error: ‘s’ was not declared in this scope
   22 |     if(s.size() == 2 && s == "00") return (qmi(4 , k - 1) + mod - 1) % mod * 4ll % mod * inv3 % mod ;
      |        ^
answer.code:22:52: error: ‘k’ was not declared in this scope
   22 |     if(s.size() == 2 && s == "00") return (qmi(4 , k - 1) + mod - 1) % mod * 4ll % mod * inv3 % mod ;
      |                                                    ^
answer.code:24:17: error: ‘s’ was not declared in this scope
   24 |     while(cnt < s.size() && s[cnt] == '0') cnt ++ ;
      |                 ^
answer.code:25:14: error: ‘k’ was not declared in this scope
   25 |     if(cnt < k * 2 - 2) return -1 ;
      |              ^
answer.code:27:25: error: ‘s’ was not declared in this scope
   27 |     for(int i = 1 ; i < s.size() ; i += 2)
      |                         ^
answer.code:35:16: error: ‘p’ was not declared in this scope
   35 |         ans += p[i / 2] * t % mod ;
      |                ^
answer.code:39:28: error: ‘k’ was not declared in this scope
   39 |     return (ans + (qmi(4 , k - 1) + mod - 1) % mod * 4ll % mod * inv3 % mod) % mod ;
      |                            ^