Farmer John lässt die Kühe verschiedene Zahlenmengen mit vorgegebener Summe suchen. Sie verwenden nur ganzzahlige Potenzen von 2. Hier sind die möglichen Mengen mit Summe 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
Hilf FJ, alle Darstellungen der ganzen Zahl $N$ ($1 \le N \le 1{,}000{,}000$) zu zählen.
Eingabe
Eine Zeile mit einer ganzen Zahl $N$.
Ausgabe
Die Anzahl Darstellungen von $N$ als angegebene Summe. Da sie sehr groß werden kann, gib nur die letzten 9 Ziffern der Dezimaldarstellung aus.
Beispiele
Eingabe 1
7Ausgabe 1
6Aufgabe 1: Summendarstellungen