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