#include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define  N 1000010

 #define mod 1000000000

 long long dp[N];

 int a[N];

 int main()

 {

     int i,j,k,n;

     while(cin>>n)

     {

         memset(dp,,sizeof(dp));

         memset(a,,sizeof(a));

         dp[] = ;

         dp[] = ;

         dp[] = ;

         dp[] = ;

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

         {

             if(i%!=)

             dp[i] = dp[i-];

             else

             {

                 dp[i] = (dp[i-]+dp[i/])%mod;

             }

         }

         cout<<dp[n]%mod<<endl;

     }

     return ;

 }