• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران

---

اگر $p = \langle p_1, p_2, \cdots, p_{3n} \rangle$ جایگشتی از اعداد $1$ تا $3n$ باشد، سیانه‌ی آن را دنباله‌ی $q = \langle q_1, q_2, \cdots, q_n \rangle$ تعریف می‌کنیم که $q_i$ در این دنباله برابر با میانه‌ی $\langle p_{3i - 2}, p_{3i - 1}, p_{3i} \rangle$ می‌باشد.

برای مثال سیانه‌ی دنباله‌ی $p = \langle 4, 8, 9, 7, 1, 3, 2, 6, 5 \rangle$ برابر با $q = \langle 8, 3, 5 \rangle$ است.

باقی‌مانده‌ی تعداد سیانه‌های متفاوت بین تمام جایگشت‌های اعداد $1$ تا $3n$ بر $10^9+7$ را پیدا کنید.

ورودی

در خط اول ورودی عدد طبیعی $n$ می‌آید. $$1 \le n \le 10^6$$

خروجی

در تنها خط خروجی باقی‌مانده تقسیم تعداد سیانه‌های متفاوت را بر $10^9+7$ خروجی دهید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۴	$n \le 4$
۲	۱۶	$n \le 300$
۳	۳۱	$n \le 3000$
۴	۴۹	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

1

خروجی نمونه ۱

1

ورودی نمونه ۲

2

خروجی نمونه ۲

8

در این نمونه، سیانه‌هایی که ساخته می شود این دنباله‌ها می‌باشد: $\langle 2, 4 \rangle$, $\langle 2, 5 \rangle$, $\langle 3, 4 \rangle$, $\langle 3, 5 \rangle$, $\langle 4, 2 \rangle$, $\langle 5, 2 \rangle$, $\langle 4, 3 \rangle$, $\langle 5, 3 \rangle$

ورودی نمونه ۳

7

خروجی نمونه ۳

141629040