+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- اگر $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 ```