#include<cstdio>
const int MOD=10000;
int n,a[105][105],s1[105][105],s2[105][105];
void read()
{
    freopen("sir23.in","r",stdin);
    freopen("sir23.out","w",stdout);
    scanf("%d",&n);
}
void init()
{
    for(int j=1;j<=n;j++)
    {
        a[1][j]=j;
        s1[1][j+1]=(s1[1][j]+a[1][j])%MOD;
        s2[1][j+1]=(s2[1][j]+(j*a[1][j])%MOD)%MOD;
        a[2][j]=(j*j)%MOD;
        s1[2][j+1]=(s1[2][j]+a[2][j])%MOD;
        s2[2][j+1]=(s2[2][j]+(j*a[2][j])%MOD)%MOD;
    }
}
void solve()
{
    for(int i=3;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            a[i][j]=(s1[i-1][j]+j*s1[i-2][j]+MOD-s2[i-2][j])%MOD;
            s1[i][j+1]=(s1[i][j]+a[i][j])%MOD;
            s2[i][j+1]=(s2[i][j]+(j*a[i][j])%MOD)%MOD;
        }
    printf("%d",a[n][n]);
}
int main()
{
    read();
    init();
    solve();
    return 0;
}