//check check check
#include<iostream>
#include<vector>
#include<algorithm>
#include<fstream>
#include<queue>
#include<cstring>
#include<map>
#include<iomanip>
#include<set>

#define ll long long
#define pb(x) push_back(x)

using namespace std;

typedef pair<int,int> ii;

const int NMAX = 1e4+5;
const int MOD = 9001;

ifstream fin("flori4.in");
ofstream fout("flori4.out");

int dp[NMAX],sp[NMAX];

//dp[i] = numarul de buchete formate cu cea mai mare floare egala cu i

int main()
{
    int N,i,j;

    fin>>N;
    if(N == 1)
    {
        fout<<1;
        return 0;
    }

    dp[1] = dp[2] = 1;
    sp[1] = 1,sp[2] = 2;
    int rez = 2;
    for(i = 3 ; i <= N ; ++i)
    {
        dp[i] = (sp[i-2] + 1)%MOD;
        sp[i] = (sp[i-1] + dp[i])%MOD;
        rez = (rez + dp[i])%MOD;
    }

    fout<<rez;
    return 0;
}