dp[i]:数字i的最多组合数
若i是奇数：i的任意一个组合都包含1，所以dp[i] = dp[i-1]
若i是偶数：i-1是奇数，任意一个组合加1构成i的组合，除了这些组合之外，i的其他组合都不包含1，意味着全部是偶数，则i/2的每个组合乘以2可以构成i的一个组合，所以dp[i]=dp[i-1]+dp[i>>1]
#include <cstdio>
const int M = 1000000000;
int main() {
	int n;
	unsigned long long *dp;
	scanf("%d", &n);
	dp = new unsigned long long[n+1];
	dp[1] = 1;
	for(int i = 2;i<=n;i++)
		dp[i] = ( i % 2 ? dp[i-1] : dp[i-1] + dp[i>>1]) % M ; 
	printf("%d\n", dp[n]);
	return 0;
}