Farmer John חתך מהמרעה כמעט בלי הגבלה ריבועי דשא בכל אורכי הצלע השלמים. לפעמים FJ אינו מפעיל את הלהב כראוי ויוצר גם ריבועים שצלעותיהם באורך 0. הוא ערם אותם בסדר, ו־Bessie הבחינה בהם אחר צהריים אחד.

Bessie תמיד רוצה דשא טעים במרעה הסודי. היא מחליטה להעביר בדיוק ארבע חתיכות ולחתוך אותן לחלקים $1\times1$ כדי לרצף את $N$ ריבועי היחידה במרעה ($1 \le N \le 10,000$).

כמה דרכים יש לבחור ארבע חתיכות לריצוף? למרעה בגודל 4 יש חמש: $(1,1,1,1)$, $(2,0,0,0)$, $(0,2,0,0)$, $(0,0,2,0)$, $(0,0,0,2)$. הסדר נחשב: $(4,3,2,1)$ שונה מ־$(1,2,3,4)$.

קלט

• שורה 1: שלם אחד $N$.

פלט

• שורה 1: שלם אחד, מספר הדרכים השונות של Bessie לבחור ארבע חתיכות דשא למרעה.

דוגמאות

קלט 1

4

פלט 1

5

מחבר הבעיה: Jeffrey Wang, 2007