dp[i][c]的含义是用2^0,2^1,...,2^i组成c的方案数
dp[0][c]是用2^0组合c的方案数，只有1种（全是1）
计算 dp[i][c]时：方案数为两部分：
第一部分是不使用 2^i，即用2^0,2^1,...,2^{i-1}组成c的方案数dp[i-1][c]
第二部分是使用 2^i，此时c保底有一个2^i，所以退化成了用2^0,2^1,...,2^{i-1}组成c-2^i的方案数dp[i-1][c-2^i]
总方案数为dp[i-1][c]+dp[i-1][c-2^i]
如果2^i>c，则是不使用2^i的情况，即dp[i-1][c]
由于提前不知道i的上限，因此去掉了i这一维，用while循环，用2^i>c作为循环终止条件，类似于空间优化版本的背包问题写法

cap = int(input().strip())

dp = [1] * (cap+1)

i = 1
while True:
    for c in range(1,cap+1):
        if 2**i > c:
            dp[c] = dp[c]
        else:
            dp[c] = (dp[c] + dp[c-2**i]) % 10**9
    i += 1
    if 2**i > cap:
        break

print(dp[cap])