اگر $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$می‌آید.

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

• زیرمسئله اول (۴ نمره): $n \leq 4$
• زیرمسئله دوم (۱۶ نمره): $n \leq 300$
• زیرمسئله سوم (۳۱ نمره): $n \leq 3000$
• زیرمسئله چهارم (۴۹ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq n \leq 1 \, 000 \, 000$

• سوال قبل
• سوال بعد