نقاشی دیواری

//Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
void debug(int out){ cerr << out << endl; }
clock_t start , stop;

#define int long long
#define loop(i , l , r) for (int i = l; i <= r; i++)
#define arc(i , r , l) for (int i = r; i >= l; i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define Turbo ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sep " "

const int Delta = 1e4+993 , mxxn = 1e4+10;
int pw (int base , int e)
{ return e? pw(base*base%Delta,e>>1)*(e&1 ? base:1)%Delta:1; }
int N , K , W , F[mxxn] , Inv[mxxn];
void get_input()
{
    cin >> K >> N >> W;
    start = clock();
} void fill_Ferma ()
{
    F[0] = 1;
    loop(i,1,mxxn-1){ F[i] = (F[i-1]*i)%Delta; }
    Inv[mxxn-1] = pw(F[mxxn-1],Delta-2);
    arc(i,mxxn-1,1){ Inv[i-1] = (Inv[i]*i)%Delta; }

} int nCr (int r , int n)
{ return r>n? 0:(F[n]*Inv[r]*Inv[n-r])%Delta; }

int subTask1 ()
{
    int dp[N+1];
    dp[0] = dp[1] = 1; dp[2] = 3;
    loop(i,3,N){
        dp[i] = ((3*dp[i-2])+(2*dp[i-3]))%Delta;
    } return dp[N]*nCr(2*N,W+1)*F[N] %Delta;
}

int subTask2 ()
{
    int dp[N+1];
    dp[0] = dp[1] = 1; dp[2] = 3; dp[3] = 15;
    loop(i,4,N){
        if (i>4){ dp[i-4] = (dp[i-5]+dp[i-4])%Delta; }
        dp[i] = ((4*dp[i-4])+(dp[i-3]*10)+(dp[i-2]*2)+dp[i-1])%Delta;
    } return dp[N]*nCr(2*N,W+1)*F[N] %Delta;
}

int subTask3 ()
{
    int dp[2*N+1][5][5][5][5];
    memset(dp,0, sizeof(dp));
    dp[0][4][4][4][4] = 1;
    loop(i,0,2*N-1){
        loop(A,0,4){
            loop(B,0,4){ if (A==4 and B<4){ continue;}
                loop(C,0,4){ if (B==4 and C<4){ continue;}
                    loop(D,0,4){ if (C==4 and D<4){ continue;}
                        dp[i][A][B][C][D] %= Delta;
                        int sz = dp[i][A][B][C][D];
                        if (A == 4){ dp[i+1][0][B][C][D] += sz; }
                        else if (B == 4){ dp[i+1][A+1][1][C][D] += sz; }
                        else if (C == 4){ dp[i+1][A+1][B+1][2][D] += sz; }
                        else if (D == 4){ dp[i+1][A+1][B+1][C+1][3] += sz; }
                        if (A!=4){ dp[i+1][B][C][D][4] += sz; }
                        if (B!=4){ dp[i+1][A][C][D][4] += sz; }
                        if (C!=4){ dp[i+1][A][B][D][4] += sz; }
                        if (D!=4){ dp[i+1][A][B][C][4] += sz; }
                    }
                }
            }
        }
    } return dp[2*N][4][4][4][4]*nCr(2*N,W)%Delta;
}

void Engine ()
{
    fill_Ferma();
    get_input();
    if (K == 1) { cout << subTask1() << endl; }
    else if (K == 2){ cout << subTask2() << endl; }
    else if (K == 3){ cout << subTask3() << endl; }
    else {
        cout << "Invalid Input :{" << endl;
    }
}

signed main()
{
    Turbo
    int Tc = 1; //cin >> Tc;
    while (Tc--){ Engine(); }
    stop = clock();
    double elapsed = (double)(stop-start)/CLOCKS_PER_SEC;
    cout << "\nTime elapsed : " << elapsed << 's';
}