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

---

اگر \(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