Farmer John każe krowom szukać różnych zbiorów liczb o zadanej sumie. Używają tylko całkowitych potęg 2. Oto możliwe zbiory o sumie 7:

1) 1+1+1+1+1+1+1

2) 1+1+1+1+1+2

3) 1+1+1+2+2

4) 1+1+1+4

5) 1+2+2+2

6) 1+2+4

Pomóż FJ policzyć wszystkie przedstawienia całkowitego $N$ ($1 \le N \le 1{,}000{,}000$).

Wejście

Jeden wiersz z jedną liczbą całkowitą $N$.

Wyjście

Liczba sposobów przedstawienia $N$ jako wskazanej sumy. Może być ogromna, więc wypisz tylko ostatnie 9 cyfr zapisu dziesiętnego.

Przykład

Wejście 1

7

Wyjście 1

6

Zadanie 1: Przedstawienia sumy