fmat

#include <fstream>
#define ULL unsigned long long int
using namespace std;
int p;
ULL F[1000001];

void fact()
{
    F[0]=1;
    for(int i=1;i<=1000000;++i)
        F[i]=((i%p)*(F[i-1]%p))%p;
    return;
}

ULL powr(ULL b,ULL e)
{
    if(e==0)
        return 1;
    if(e%2==0)
        return powr(((b%p)*(b%p))%p,e/2)%p;
    return  ((b%p)*powr(((b%p)*(b%p))%p,(e-1)/2)%p)%p;
}

ULL Comb(ULL n,ULL k)
{
    return ((F[n]%p)*(((powr(F[n-k]%p,p-2)%p)*(powr(F[k],p-2)%p))%p))%p;
}

int main()
{
    int t;
    ifstream f("fmat.in");
    f>>t>>p;
    fact();
    ofstream g("fmat.out");
    int m,n,c,k;
    while(t--)
    {
        f>>m>>n>>c>>k;
        if(k>n)
            g<<"0\n";
        else
            g<<(((Comb(n,k)%p)*((powr(c%p,k)%p)*(powr((powr(c%p,m)%p-c%p)%p,n-k))%p))%p)%p<<'\n';
    }
    return 0;
}