PROG-T1172: Crystal

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
const int MD = 10001;

int dp[N + 1], qs[N + 1];

int main(){

    int x;
    scanf("%d", &x);
    if(x == 1){
        cout << '1';
        return 0;
    }
    dp[2] = 1;
    qs[2] = 1;
    qs[3] = 1;
    for(int i = 3; i <= x; ++i){
        for(int j = 2; j <= i; ++j){
            dp[j] = (MD + qs[i] - qs[j - 2]) % MD;
        }
        for(int j = 2; j <= i + 1; ++j){
            qs[j] = (qs[j - 1] + dp[j]) % MD;
        }
    }
    int ans = 0;
    for(int i = 2; i <= x; ++i){
        ans = (ans + i * dp[i]) % MD;
    }
    cout << ans;

    return 0;
}