נתון מספר $n$. משימתכם היא לספור את כל הסדרות המשולשיות ולהדפיס את השארית מחלוקת מספרן ב-$10^9 + 7$. סדרה נקראת משולשית אם היא מקיימת את התנאים הבאים:

• אורך הסדרה אינו עולה על $n$.
• כל איבר הוא מספר שלם מהקטע $[1, n]$.
• שלושה איברים כלשהם בסדרה זו יכולים להיות אורכי הצלעות של משולש לא מנוון*.

דוגמאות לסדרות משולשיות עבור $n = 100$ הן $(1, 1, 1)$ ו-$(16, 1, 11, 25, 100)$. בראשונה, צלעות המשולש הלא מנוון הן $(1, 1, 1)$, ובשנייה הן $(16, 11, 25)$.

הסדרה $(16, 1, 11, 84, 100)$ אינה משולשית, משום שאין שלושה איברים היוצרים צלעות של משולש לא מנוון. גם הסדרה $(5, 5)$ אינה משולשית.

* משולש הוא לא מנוון אם יש לו שטח חיובי. באופן שקול, קודקודיו אינם נמצאים על ישר אחד.

קלט

השורה היחידה מכילה מספר שלם $n$ ($3 \le n \le 200\,000$).

פלט

הדפיסו מספר שלם יחיד – השארית מחלוקת מספר הסדרות המשולשיות ב-$10^9 + 7$ (כלומר, $1000000007$).

דוגמאות

קלט 1

3

פלט 1

15

קלט 2

4

פלט 2

254

הערה

עבור $n = 3$ ישנן $15$ סדרות משולשיות: $(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,1), (2,2,2), (2,2,3), (2,3,2), (2,3,3), (3,1,3), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3)$.

עבור $n = 4$ ישנן $254$ סדרות משולשיות: $(1,1,1), (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,1,4), (1,1,2,1), \dots, (4,4,2,4), (4,4,3), (4,4,3,1), (4,4,3,2), (4,4,3,3), (4,4,3,4), (4,4,4), (4,4,4,1), (4,4,4,2), (4,4,4,3), (4,4,4,4)$.