#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 5 , MOD =  1e9 + 7;

ll power(ll x , ll y , ll MOD )
{
    ll res =1;
    while ( y )
    {
        if( y&1 ) res = res * x % MOD  ;

        y >>= 1;
        x = x * x % MOD ;
    }

    return res;
}

int32_t main() {

    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);


    ll phi = 1;

    int nn = 59964251 ;
    for(int i = 2 , d= 1 ; i*i <= nn ; i+=d , d = 2)
    {
        if(nn%i == 0)
        {
            ll p_to_k = 1;
            while(nn%i == 0) p_to_k *= i , nn /= i ;
            phi *= (p_to_k/i ) * (i-1) ;
        }
    }

    if(nn > 1) phi *= nn-1;


    int t =1;
    cin >> t;
    while (t--)
    {
        string n ;

        int m , d , k ;
        cin >> n >> m >> d >> k ;

        ll po[m+1] ;
        po[0] = 1 ;
        for(int i= 1; i <= m ; i++) po[i] = power( i , k ,59964251 ) ;

        ll sum[m+1] ;
        sum[0] =0 ;
        for(int i= 1; i <= m ;i++) sum[i] = (sum[i-1] + po[i]) % 59964251 ;

        int exp =0 ;

        for(char c : n) exp *= 10 , exp += (c - '0' ) , exp %= phi ;

        for(int i =1;  i<= m ;i++) sum[i] = power( sum[i] , exp + phi ,  59964251 ) ;

        vector<int> ans(m+1) ;

        for(int i= m ; i >= d ; i--)
        {
            if( i%d ) continue;

            ans[i] = sum[ m/i ] * power( power( i , k , 59964251 ) , exp + phi , 59964251) % 59964251 ;

            for(int j = i +i ; j <= m ; j += i) ans[i] -= ans[j] , ans[i] += 59964251 , ans[i] %= 59964251 ;

        }

        cout << ans[d]  << "\n" ;
    }

    return 0;
}