Farmer John demande aux vaches de chercher différents ensembles de nombres dont la somme est donnée. Elles n'utilisent que des puissances entières de 2. Voici les ensembles possibles de somme 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

Aidez FJ à compter toutes les représentations de l'entier $N$ ($1 \le N \le 1{,}000{,}000$).

Entrée

Une ligne contenant un seul entier $N$.

Sortie

Le nombre de façons de représenter $N$ par cette somme. Ce nombre pouvant être immense, n'affichez que les 9 derniers chiffres de son écriture décimale.

Exemples

Entrée 1

7

Sortie 1

6

Problème 1 : Décompositions en sommes