#include<bits/stdc++.h> using namespace std; int f[1000001]; int main() { int n; cin>>n; f[0]=1; for(int i=1;i<=n;i*=2) for(int j=i;j<=n;j++) f[j]=(f[j]+f[j-i])%1000000000; cout<<f[n]; }