//
//  main.cpp
//  piramida1
//
//  Created by Casuneanu Andrei on 05/02/14.
//  Copyright (c) 2014 Casuneanu Andrei. All rights reserved.
//

#include <fstream>
#define IN "piramida1.in"
#define OUT "piramida1.out"
#define MOD 10000
#define NCOMB 22
#define NMAX 600008
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

int s;
int put;
int hmax;
int comb[NCOMB][NCOMB];
int nr[NMAX];

void citire();
void combinari();
void showtime();


int main(int argc, const char * argv[])
{
	citire();
	if (s<=0) {fout <<1<<'\n';fout.close(); return 0;}
	combinari();
	showtime();
    return 0;
}

void showtime()
{
	//cate moduri pt a scrie s ca suma de oricate combinari
	int i, k;
	nr[0]=1;
	for (i=1; i<=hmax; i++)
		for (k=comb[hmax][i]; k<=s; k++)
			nr[k]=(nr[k]+nr[k-comb[hmax][i]])%MOD;
	
	fout <<nr[s]<<'\n';
	fout.close();
}

void combinari()
{
	int i, j;
	comb[2][1]=comb[2][2]=1;
	for (i=3; i<NCOMB; i++)
	{
		comb[i][1]=comb[i][i]=1;
		for (j=2; j<i; j++)
			comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%MOD;
	}
}

void citire()
{
	fin >>s;

	for (put=2, hmax=1; put<=s; put*=2, hmax++);
	s-=put/2;
}