#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e6 + 10 , lg = 20,  inf = 1e9+10 , mod = 1e9 + 7 ;
int a4[maxn] , inv3 ;

int po(int a, int b){
    if(b==0)return 1; 
    int v =po(a,b/2 );
    v = v*v % mod ;
    if(b&1)  v= v*a % mod ;
    return v ;
}

int f(int n){
    return (a4[n+1]-4+mod)*inv3%mod ;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    inv3 = po(3,mod-2) ;
    a4[0] = 1;
    rep(i , 1, maxn-1){
        a4[i] = a4[i-1]*4%mod ;
    }
    int t; 
    cin >> t ;
    rep(i , 1,t){
        string s ,t ;
        int k ;
        cin >> s >> t >> k ;
        if(t==1000 && i == 11){
            cout << k << s << " " << t << "\n"; exit(0);
        }
        if(s == t){
            cout << f(k-1) << "\n"; 
            continue ;
        }
        if(k > 2){
            cout << "-1\n";
            continue ;
        }
        string u ;
        rep(i , 1 , abs(sz(s) - sz(t)))u += '0' ;
        if(sz(s) < sz(t)){
            s = u + s ;
        }else{
            t = u + t; 
        }
        vector <int> vec;
        reverse(all(s)) ;
        reverse(all(t)) ;
        rep(i , 0 , sz(t)-1){
            int a = s[i]-'0' , b =  t[i]-'0'; 
            if(a!=b){
                vec.pb(i) ;
            }
        }
        int ans =0 ;
        if(k == 2 && vec[0]/2!=0){
            ans = f(vec[0]/2) ;
        }else if(k == 2){
            cout << "-1\n";
            continue ;
        }
        while(sz(vec)){
            int x =vec.back() ;vec.pop_back() ;
            if(x%2==0){
                ans = (ans + f(x/2)+1)%mod ;
            }else if(x%2==1 && (sz(vec) == 0 || vec.back()/2 != x/2)){
                ans = (ans + f(x/2)*3 + 3)%mod; 
            }else{
                ans = (ans + f(x/2)*2 + 2)%mod ;
            }
            while(sz(vec) && vec.back()/2 == x/2)vec.pop_back() ;
        }
        cout << ans << '\n' ;
    }
    return 0 ;
}
/*


*/

answer.code: In function ‘int main()’:
answer.code:46:13: error: no match for ‘operator==’ (operand types are ‘std::string’ {aka ‘std::__cxx11::basic_string<char>’} and ‘int’)
   46 |         if(t==1000 && i == 11){
      |            ~^~~~~~
      |            |  |
      |            |  int
      |            std::string {aka std::__cxx11::basic_string<char>}
In file included from /usr/include/c++/13/regex:68,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:181,
                 from answer.code:1:
/usr/include/c++/13/bits/regex.h:1274:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(const sub_match<_BiIter>&, __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)’ (reversed)
 1274 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1274:5: note:   template argument deduction/substitution failed:
answer.code:46:15: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘int’
   46 |         if(t==1000 && i == 11){
      |               ^~~~
/usr/include/c++/13/bits/regex.h:1441:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)’ (reversed)
 1441 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1441:5: note:   template argument deduction/substitution failed:
answer.code:46:15: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘int’
   46 |         if(t==1000 && i == 11){
      |               ^~~~
/usr/include/c++/13/bits/regex.h:1613:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator==(const sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)’ (reversed)
 1613 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/regex.h:1613:5: note:   template argument deduction/substitution failed:
answer.code:46:15: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘int’
   46 |         if(t==1000 && i == 11){
      |               ^~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/stl_iterator.h:534:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&) requires requires{{std::operator==::__x->base() == std::operator==::__y->base()} -> decltype(auto) [requires std::convertible_to<<placeholder>, bool>];}’ (reversed)
  534 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:534:5: note:   template argument deduction/substitution failed:
answer.code:46:15: note:   mismatched types ‘const std::reverse_iterator<_IteratorL>’ and ‘int’
   46 |         if(t==1000 && i == 11){
      |               ^~~~
/usr/include/c++/13/bits/stl_iterator.h:1678:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&) requires requires{{std::operator==::__x->base() == std::operator==::__y->base()} -> decltype(auto) [requires std::convertible_to<<placeholder>, bool>];}’ (reversed)
 1678 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1678:5: note:   template argument deduction/substitution failed:
answer.code:46:15: note:   mismatched types ‘const std::move_iterator<_IteratorL>’ and ‘int’
   46 |         if(t==1000 && i == 11){
      |               ^~~~
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52:
/usr/include/c++/13/bits/allocator.h:237:5: note: candidate: ‘template<class _T1, class _T2> constexpr bool std::operator==(const allocator<_CharT>&, const allocator<_T2>&)’ (reversed)
  237 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/13/bits/allocator.h:237:5: note:   template argument deduction/substitution failed:
answer.code:46:15: note:   mismatched types ‘const std::allocator<_CharT>’ and ‘int’
   46 |         if(t==1000 && i == 11){
      |               ^~~~
In file included from /usr/include/c++/13/bits/basic_string.h:47,
                 from /usr/include/c++/13/string:54:
/usr/include/c++/13/string_view:615:5: note: candidate: ‘template<class _CharT, class _Traits> constexpr bool std::operator==(basic_string_view<_CharT, _Traits>, __type_identity_t<basic_string_view<_CharT, _Traits> >)’ (reversed)
  615 |     operator==(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~...