#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 ;
}
/*


*/