1318 - Strange Game_WA

//http://www.lightoj.com/volume_showproblem.php?problem=1318
#include<algorithm>
#include<stdio.h>
#include<vector>
using namespace std;
typedef long long int LLI;
typedef pair<int,int> PII;
#define REP(i,n) for(int i=0;i<n;i++)
#define PB push_back
#define MP make_pair
#define Mx 100003
#define MxS 320
vector<PII>V[Mx+9];
int T[Mx+9];
bool vis[Mx+9];
void precal()
{
    int ct;
    REP(i,Mx)T[i]=i;
    for(int i=2;i<=MxS;i++)
    {
        if(!vis[i])
        {
            for(int j=i+i;j<=Mx;j+=i)
            {
                ct=0;
                while(T[j]%i==0)
                {
                    ct++;
                    T[j]/=i;
                }
                V[j].PB(MP(i,ct));
                vis[j]=1;
            }
        }
    }
    for(int i=2;i<Mx;i++)
    {
        if(!vis[i])
        {
            V[i].PB(MP(i,1));
        }
        else if(T[i]!=1)
        {
            V[i].PB(MP(T[i],1));
        }
    }
}

template<class T> inline T BIGMOD(T n, T m, T mod)
{
    if(m<0)return 1;
    LLI ans = 1;
    LLI k = n;
    while(m){
        if(m & 1) {
            ans *= k;
            if(ans>mod) ans %= mod;
        }
        k *= k;
        if(k>mod) k %= mod;
        m >>= 1;
    }
    return ans;
}

long long nCr(LLI n,LLI r,LLI modv)
{
    if(r==0)return 1%modv;
    REP(i,Mx)T[i]=0;
    for(int i=max(r,n-r)+1;i<=n;i++)
    {
        for(int j=V[i].size()-1;j>=0;j--)
        {
            T[V[i][j].first]+=V[i][j].second;
        }
    }
    for(int i=min(r,n-r);i>=2;i--)
    {
        for(int j=V[i].size()-1;j>=0;j--)
        {
            T[V[i][j].first]-=V[i][j].second;
        }
    }
    LLI ret=1;
    for(int i=2;i<Mx;i++)
    {
        if(T[i] && !vis[i])
        {
            ret=(ret * BIGMOD((LLI)i,(LLI)T[i],modv))%modv;
        }
    }
    return ret;
}


int main()
{
    //read(inp);
    //write(out);
    precal();
    int kase,ks=0;
    scanf("%d",&kase);
    while(kase--)
    {
         LLI N,K,L,M;
         scanf("%lld %lld %lld %lld",&N,&K,&L,&M);
         LLI fu=(K)*(K-1);
         //cout << fu << "......." << endl;
         //fu>>=1;
         LLI gg=fu/2;//m
         LLI res=nCr(L,L-M,N);
         res = (res * BIGMOD(K,L-M,N))%N;
         res = (res * BIGMOD(gg,M,N))%N;
         res = (res * BIGMOD(2LL,M-1,N))%N;
         //cout << nCr(L,L-M,N) << " -> " << power(K,L-M) << " " << (fu * M) << endl;
         printf("Case %d: %lld\n",++ks,(res%N)+1LL);
    }
    return 0;
}