N = 25
M = int(1e6 + 10)
mod = int(1e9)
p = [1] * N
f = [[0] * M for i in range(N)]     #f[i][j]表示前i个p和为j的方法数
for i in range(1, N):
    p[i] = p[i - 1] * 2

n = int(input())
for i in range(N):
    f[i][0] = 1
for i in range(N):
    for j in range(n + 1):
        if j >= p[i]:
            f[i][j] = (f[i - 1][j] + f[i][j - p[i]]) % mod
        else:
            f[i][j] = f[i - 1][j]

print(f[N - 1][n])