Farmer John manda as vacas buscar conjuntos diferentes de números cuja soma seja um número dado. Só usam potências inteiras de 2. Estes são os conjuntos possíveis que somam 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

Ajude FJ a contar todas as representações do inteiro $N$ ($1 \le N \le 1{,}000{,}000$).

Entrada

Uma linha com um único inteiro $N$.

Saída

O número de formas de representar $N$ como a soma indicada. Pode ser enorme, portanto imprima apenas os últimos 9 dígitos decimais.

Exemplos

Entrada 1

7

Saída 1

6

Problema 1: Decomposições em somas