# 백준 2410번 2의 멱수의 합
n = int(input())

dp = [0] * (n +1)

dp[0] = 1
# i가 홀수 일 때는 dp[i-1]과 같고
# 짝수 일 때는 거기에다가 dp[i//2]를 더한다.
# // 연산자는 몫의 정수 부분만 남긴다. 즉 int(i/2)와 같음.
# i & 1 은 비트 and 연산자로 홀수 일 때는 마지막 비트가 1이니 값이 1이되고
# 짝수일때는 마지막 값이 0이니 0이 된다. 즉 짝수일대라는 뜻.
# 다른 사람 코드를 들고 온건데 너무 짧고 예쁘고 아름다운 코드라 많은 공부가된듯.
for i in range(1, n+1):
    dp[i] = (dp[i-1] + (i & 1 == 0 and dp[i//2] )) % 1000000000

print(dp[n])