آرایه $a$ شامل اعداد $a_1, a_2, …, a_n$ را در نظر بگیرید، به دنباله ناتهی $x_1, x_2, …, x_k$ از اعداد $1$ تا $n$ تورج‌پسند گفته می‌شود، اگر

• $1 \le x_1 < x_2 < … < x_k \le n$.
• $a_{x_1} \le a_{x_2} \le … \le a_{x_n}$.
• برای هر $1 \le i < k$ و هر $x_i < j < x_{i+1}$ داشته باشیم $a_{x_i} \le a_j \le a_{x_{i+1}}$.

آقا تورج برای استخدام کارمند در شرکتش، آرایه $a$ را به مراجعین می‌دهد و در صورتی که بتوانند باقی‌مانده تعداد دنباله‌های تورج‌پسند آن را بر $10 ^ 9 + 7$ بیابند آن‌ها را استخدام می‌کند.

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

خط اول ورودی شامل عدد $n$ است که طول آرایه $a$ را مشخص می‌کند.

در خط دوم $n$ عدد $a_1, a_2, …, a_n$ می‌آید.

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

• زیرمسئله اول (۷ نمره): $n \leq 20$.
• زیرمسئله دوم (۱۵ نمره): $n \leq 5000$.
• زیرمسئله سوم (۷۸ نمره): بدون محدودیت اضافی.

• $1 \le n \le 5 \times 10^{5}$.
• $1 \le a_i \le 10^9$.