/*

8=1+1+1+1+1+1+1+1+1   1

8=1+1+1+1+1+1+1+2      2 3

8=1+1+1+1+2+2

8=1+1+1+1+4                4 5

8=1+1+2+2+2

8=1+1+2+4                   6 7

8=2+2+2+2

8=2+2+4

8=4+4

8=8                             8~9

*/

/*

以下引用自博客：http://blog.csdn.net/scorpiocj/article/details/5940456

如果i为奇数，肯定有一个1，把f[i-1]的每一种情况加一个1就得到fi,所以f[i]=f[i-1]

如果i为偶数，如果有1，至少有两个，则f[i-2]的每一种情况加两个1，就得到i，如果没有1，则把分解式中的每一项除2，则得到f[i/2]

所以f[i]=f[i-2]+f[i/2]

由于只要输出最后9个数位，别忘记模1000000000

*/

#include<iostream>

#include<string>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

int a[];

int main()

{

    a[]=;a[]=;

    for(int i=;i<;i++)

    {

        if(i%)a[i]=a[i-];

        else a[i]=(a[i-]+a[i/])%;

    }

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        printf("%d\n",a[n]);

    }

    return ;

}