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

اگر p=p1,p2,,p3np = \langle p_1, p_2, \cdots, p_{3n} \rangle جایگشتی از اعداد 11 تا 3n3n باشد، سیانه‌ی آن را دنباله‌ی q=q1,q2,,qnq = \langle q_1, q_2, \cdots, q_n \rangle تعریف می‌کنیم که qiq_i در این دنباله برابر با میانه‌ی p3i2,p3i1,p3i\langle p_{3i - 2}, p_{3i - 1}, p_{3i} \rangle می‌باشد.

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

باقی‌مانده‌ی تعداد سیانه‌های متفاوت بین تمام جایگشت‌های اعداد 11 تا 3n3n بر 109+710^9+7 را پیدا کنید.

ورودی

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

خروجی

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

زیرمسئله‌ها

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

مثال

ورودی نمونه ۱

1
Plain text

خروجی نمونه ۱

1
Plain text

ورودی نمونه ۲

2
Plain text

خروجی نمونه ۲

8
Plain text

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

ورودی نمونه ۳

7
Plain text

خروجی نمونه ۳

141629040
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.