يربي Farmer John أبقاره للتكاثر. تستخدم التقنيات الحديثة ثيراناً حائزة جوائز ماتت منذ زمن، فلا حاجة لثيران. يضبط عدد العجول بكمية الطعام؛ يطعم الجميع المقدار نفسه فتنتج كل بقرة العدد نفسه. يبدأ ببقرة واحدة ويريد $N$ أبقار بعد عدة أجيال.

إذا $N = 12$، يطعم الأصلية لتنتج ثلاثة عجول. حين يبلغ الجيل التالي سن التكاثر، يطعم كل واحدة لتنتج أربعة، فيحصل على اثني عشر في النهاية. تباع البقرة بعد إنتاج نسلها، ويبقي أحدث جيل فقط.

في كل جيل تنتج كل بقرة عجلين على الأقل بلا حد أعلى، إذ يستخدم سلالة قوية جداً.

لعدد صحيح $N$ ($1 \le N \le 2{,}000{,}000{,}000$)، كم طريقة مختلفة للحصول على $N$ أبقار بدءاً بواحدة؟ لا يتجاوز عدد طرق الحصول على $N$ $2{,}000{,}000{,}000$.

الإدخال

• السطر 1: العدد الصحيح $N$.

الإخراج

• السطر 1: عدد طرق الحصول على $N$ أبقار.

أمثلة

الإدخال 1

12

الإخراج 1

8

ملاحظة

تفاصيل الإخراج

طريقة للحصول على اثني عشر هي $(2,2,3)$: عجلان لكل بقرة في الجيل الأول، عجلان في الثاني، وثلاثة في الثالث، أي اثنا عشر عجلًا صغيراً. الطرق السبع الأخرى $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

المؤلف: Mihai Stroe، 2002