====== سیانه (Siane) ======
اگر 
$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$

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|1|1|
|2|8|
|7|141629040|
</WRAP>

  * [[سوال ۱|سوال قبل]]
  * [[سوال ۳|سوال بعد]]