+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --- محمدسام بعد از تساوی غیرمنتظره اسپانیا در برابر کیپ‌ورد با عملکرد خیلی خوب وُزینیا (دروازه‌بان کیپ‌ورد) دیگر اشتیاقی برای نوشتن داستان جذاب برای سوال نداشت. به همین دلیل سعی کرد برای جلوگیری از اتلاف وقت، متن این سوال را به خلاصه‌ترین حالت ممکن بنویسد: به شما یک جایگشت به طول $n$ به نام $p$ ورودی داده شده و شما قرار است فرآیند گفته شده را بر روی این جایگشت انجام دهید: + ابتدا تعدادی از اعضای آن را حذف کنید (این تعداد می‌تواند 0 هم باشد) به طوری که حداقل یک عضو از این جایگشت باقی بماند. + سپس آرایه باقیمانده را $a$ بنامید. شما می‌توانید بر روی آرایه باقیمانده عملیات زیر را به تعداد دلخواه (این تعداد می‌تواند 0 هم باشد) انجام دهید: + + فرض کنید طول آرایه $k$ باشد. شما یک اندیس $i$ انتخاب می‌کنید به طوری که $1 < i$ و $i < k$ باشد و همچنین عضو $i$‌ام آرایه از هر دو عضو مجاورش اکیداً بزرگ‌تر باشد، سپس مقدار این عضو را برابر با $0$ قرار می‌دهید. حال در این سوال شما باید تعداد آرایه‌های مختلفی که با استفاده از فرآیند بالا بر روی جایگشت $p$ قابل به دست آمدن هستند را محاسبه کنید. از آنجا که این مقدار عدد بزرگی است، کافیست باقیمانده آن را بر $10^9+7$ خروجی دهید.  # ورودی ورودی به صورت $T$ تست‌کیس مختلف می‌آید که برای هرکدام باید مسئله را جداگانه حل کنید. در خط اول ابتدا عدد $T$ و سپس در $2 \cdot T$ خط بعد به ترتیب برای هر تست‌کیس عدد $n$ و سپس در خط بعد $n$ عدد متمایز می‌آید که نشان‌دهنده جایگشت $p$ است. $$ 1 \leq T \leq 100 $$ $$1 \leq n \leq 5000 $$ $$ 1 \leq p_i \leq n $$ تضمین می‌شود جمع مقادیر $n$ بر روی همه تست‌کیس‌ها حداکثر $5000$ است. تضمین می‌شود در هر تست‌کیس تمامی $p_i$ ها متمایز هستند. # خروجی در یک خط، باید تعداد $a$ های مختلفی که قابل به دست آمدن هستند را باقیمانده بر $10^9 + 7$ خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 2 2 1 3 1 3 2 5 1 4 3 2 5 ``` ## خروجی نمونه ۱ ``` 3 8 39 ```