#include <iostream>

using namespace std;
const int mod=1e9;
const int N=1e6+1e4;
int n;
int dp[N];//方案个数
int v[25];
int main()
{
    v[1]=1;
    for(int i=2; i<22; i++)
    {
        v[i]=v[i-1]*2;
        //cout<<v[i]<<endl;
    }
    cin>>n;
    dp[0]=1;
    for(int i=1; i<22; i++)
    {
        for(int j=v[i]; j<=n; j++)//从v[i]开始
        {
//            for(int k=0; k*v[i]<=j; k++)
//            {
//                //dp[i][j]=max(dp[i+1][j-k*v[i]]+k,dp[i][j]);
//                dp[i][j]=(dp[i][j]+dp[i-1][j-k*v[i]])%mod;//将k的所有情况相加
//            }
            //递推
            dp[j]=(dp[j]+dp[j-v[i]])%mod;
        }
    }
    cout<<dp[n]<<endl;;
    //cout << "Hello world!" << endl;
    return 0;
}