أُعطي عدد $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)$.