Strange Game

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<29)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define REP(i, n) FOR(i, 0, n)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX int(1e5+5)
int l[MX],H[MX],C[MX][8],f[MX][8];
void gen(void){
    F(MX)H[i]=i;
    for(int i(2);i<MX;++i)if(H[i]>1)
        for(int j(i),c(0);j<MX;j+=i,c=0){
            while(!(H[j]%i))H[j]/=i,++c;
            if(c)C[j][l[j]]=c,f[j][l[j]++]=i;
        }
}
ll MOD;
ll pw(ll n,ll k){
    ll r(1);
    while(k){
        if(k&1)
            r*=n,r%=MOD;
        n*=n,n%=MOD;
        k>>=1;
    }
    return r;
}
int F[MX];
ll sl(ll N,ll K,ll L,ll M){
    if(!M)return pw(K,L);
    CL(F,0);
    ll S(1),U(max(L-M,M)),W(min(L-M,M)),A,B;
    FT(U+1,L+1)F(l[k])F[f[k][i]]+=C[k][i];
    FT(2,W+1)F(l[k])F[f[k][i]]-=C[k][i];
    F(L+1)if(F[i])S*=pw(i,F[i]),S%=MOD;
    if(!(K&1))A=(pw(K,L-1)*K/2)%MOD,B=pw(K-1,M);
    else A=pw(K,L),B=(pw(K-1,M-1)*(K-1)/2)%MOD;
    return (((S*A)%MOD)*B)%MOD;
}
int main(void){
    ll N,K,L,M;
    gen();
    IN(tt)F(tt)
        scanf("%lld%lld%lld%lld",&N,&K,&L,&M),MOD=N,
        printf("Case %d: %lld\n",i+1,1+sl(N,K,L,M));
    return 0;
}