Farmer John pide a las vacas conjuntos diferentes de números cuya suma sea un número dado. Solo usan potencias enteras de 2. Estos son los conjuntos posibles que suman 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

Ayuda a FJ a contar todas las representaciones del entero $N$ ($1 \le N \le 1{,}000{,}000$).

Entrada

Una línea con un único entero $N$.

Salida

El número de formas de representar $N$ como dicha suma. Puede ser enorme, así que imprime solo las últimas 9 cifras decimales.

Ejemplos

Entrada 1

7

Salida 1

6

Problema 1: Descomposiciones en sumas