Description

Given an integer $N$, how many ways are there to decompose $N$ into a sum of several powers of $2$?

Input Format

Input an integer $N$ ($1 \leq N \leq 10^6$).

Output Format

Output the number of valid decompositions modulo $10^9$.

7

6

Hint

All valid decompositions are as follows.

• 1+1+1+1+1+1+1
• 1+1+1+1+1+2
• 1+1+1+2+2
• 1+1+1+4
• 1+2+2+2
• 1+2+4

Translated by ChatGPT 5