بعد از اتمام لیگ بزرگ کرانکر، تمام شرکت‌کنندگان مسابقه برای اعلام نتایج در یک ردیف روی سکو ایستاده‌اند.

بلافاصله بعد از اعلام نتایج، هیاهوی عظیمی بر روی سکو شکل می‌گیرد. رتبه نفر $i$ ام در صف $p_i$ است. هر یک از این $n$ شرکت‌کننده ممکن است برای بهتر کردن جایگاه خود بازیکنان دیگر را به قتل برسانند.

بازیکنی که قصد جان بازیکنان دیگر را کرده است به این صورت قربانی خود را انتخاب می‌کند؛ ابتدا رو به یکی از دو انتهای صف می‌ایستد. سپس از بین کسانی که در دیدش قرار دارند، فرد با بهترین رتبه را انتخاب می‌کند و یک چاقو به سمت او پرتاب می‌کند. از آنجا که این لیگ مختص بازیکنان رده بالاست و هدف قرار دادن یک نفر در میان صف کاری نه‌چندان دشوار است، چاقو حتما به هدف اصابت کرده و باعث پایین افتادن قربانی از روی سکو می‌شود.

توجه کنید که می‌توان فرض کرد که پرتاب‌ها به نوبت انجام می‌شوند، یعنی قبل از اینکه پرتاب یک بازیکن به هدف اصابت کند بازیکن دیگری پرتاب نخواهد کرد. مشخص است کسی که چاقو خورده از سکو پایین افتاده و بعد از این نمی‌تواند چاقویی پرتاب کند. نه تنها ممکن است یک بازیکن بیشتر از یک بار چاقو پرتاب کند، بلکه می‌تواند این چاقو‌ها را در جهات متفاوت پرتاب کند.

از آنجایی که در مراسمی به این بزرگی هر نوعی از سرگرمی پیدا می‌شود احتمال دارد حضور نیرو‌های امنیتی با مقداری تاخیر مواجه شود. آشمز که مسئولیت اجرای این مراسم را بر عهده دارد می‌خواهد بداند تا زمان ورود نیرو‌های امنیتی، مجموعه‌ی بازیکنان روی سکو چند حالت مختلف می‌تواند داشته باشد.

در خط اول ورودی عدد طبیعی $n$ می‌آید.

در خط دوم جایگشت $p$ به صورت $p_1, p_2, \ldots, p_n$ به‌ترتیب می آید.

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

• زیرمسئله اول (۱۵ نمره): $n \leq 500$
• زیرمسئله دوم (۲۵ نمره): $n \leq 5000$
• زیرمسئله سوم (۶۰ نمره): بدون محدودیت اضافی

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

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