Farmer John ordina alle mucche di cercare diversi insiemi di numeri con una somma data. Usano solo potenze intere di 2. Ecco i possibili insiemi con somma 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

Aiuta FJ a contare tutte le rappresentazioni dell'intero $N$ ($1 \le N \le 1{,}000{,}000$).

Input

Una riga con un solo intero $N$.

Output

Il numero di modi di rappresentare $N$ come la somma indicata. Può essere enorme, quindi stampa solo le ultime 9 cifre decimali.

Esempi

Input 1

7

Output 1

6

Problema 1: Decomposizioni in somme