py3 代码

N = 1e9
n = int(input())
a = [2 ** i for i in range(int(math.log(n, 2)) + 1)]
f = [0] * (n + 1)
f[0] = 1

for i in range(len(a)):
    for j in range(a[i], n + 1):
        f[j] = int((f[j] + f[j - a[i]]) % N)

print(f[n])