• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

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

• برای هر $1 \le i < k$ و هر $x_i < j < x_{i+1}$ داشته باشیم $a_{x_i} \le a_j \le a_{x_{i+1}} ; ;$

• $1 \le x_1 < x_2 < ... < x_k \le n$

• $a_{x_1} \le a_{x_2} \le ... \le a_{x_n}$

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

ورودی

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

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

خروجی

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

زیر مسئله ها

زیرمسئله	نمره	محدودیت ها
۱	۷	$n \le 20$
۲	۱۵	$n \le 5000$
۳	۷۸	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3
1 2 3

خروجی نمونه ۱

7

ورودی نمونه ۲

4
5 2 1 6

خروجی نمونه ۲

5