أمر Farmer John الأبقار بالبحث عن مجموعات أعداد مختلفة مجموعها عدد معين. تستخدم فقط قوى 2 ذات الأس الصحيح. هذه المجموعات الممكنة التي مجموعها 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

ساعد FJ في عد جميع تمثيلات الصحيح $N$ ($1 \le N \le 1{,}000{,}000$).

الإدخال

سطر واحد يحوي صحيحًا واحدًا $N$.

الإخراج

عدد طرق تمثيل $N$ بالمجموع المذكور. قد يكون هائلًا، لذا اطبع آخر 9 خانات من تمثيله العشري فقط.

أمثلة

الإدخال 1

7

الإخراج 1

6

المسألة 1: تمثيلات المجموع