include[HTML_REMOVED]
define N 1000000000
using namespace std;
typedef long long ll;
int n;
ll dp[1000010];
int main()
{
scanf(“%d”,&n);
int t=n,cnt=0;
while(t)
{
t/=2;
cnt;
}
cnt-=1;
dp[0]=1;
for(int i=0;i<=cnt;i)
for(int j=(1<<i);j<=n;j++)
dp[j]=(dp[j]+dp[j-(1<<i)])%N;
printf(“%lld”,dp[n]);
return 0;
}