• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

یک جدول $3 \times n$ داریم. بیت‌پین می‌خواهد تعدادی از خانه‌های جدول را برای عید از سماق پر کند. او به تازگی یاد گرفته است که زیبایی همیشه در تقارن نیست و گاهی زیبایی در بی‌نظمی است. برای همین نگران است که نکند ۴ خانه از خانه‌های جدول باشند که از سماق پر شده باشند و چهار گوشه یک مستطیل از خانه‌های جدول را تشکیل دهند.

سماق نماد صبر و بردباری است.

با توجه به اینکه بیت‌پین خیلی پولدار است و می‌خواهد بیشترین تعداد خانه را از سماق پر کند به او بگویید چند روش مختلف برای پر کردن خانه‌های جدول از سماق وجود دارد که بیشترین میزان ممکن سماق پر شده باشد و همچنین شرایط بی‌نظمی نیز برقرار باشد.

چون ممکن است تعداد روش‌ها بسیار زیاد باشد، باقی‌مانده این تعداد بر $+ 7$ ${10}^9$ را چاپ کنید.

ورودی

در سطر اول عدد صحیح $n$ می‌آید که نشان‌دهنده طول جدول است.

$$1 \le n \le 100 , 000$$

خروجی

در یک سطر تعداد روش‌های پر کردن سماق در جدول را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

1

خروجی نمونه ۱

1

ورودی نمونه ۲

5

خروجی نمونه ۲

540