Сэрэжад $n$ урттай эерэг бүхэл тоон дараалал $a_{1}, a_{2}, ..., a_{n}$ өгөгджээ.

Эхлээд Сэрэжа дөрвөлжин цаасан дээр $a$-ийн бүх ялгаатай, хоосон биш, үл буурах дэд дарааллуудыг бичжээ. Тэгээд цаасан дээрх дараалал тус бүрт харгалзуулан түүнээс хэтрэхгүй бүх дарааллуудыг туузан цааснууд дээр бичжээ.

$x_{1} ≤ y_{1}, x_{2} ≤ y_{2}, ..., x_{r} ≤ y_{r}$ нөхцөл биелж байвал эерэг тоон дараалал $x = x_{1}, x_{2}, ..., x_{r}$ нь эерэг тоон дараалал $y = y_{1}, y_{2}, ..., y_{r}$-ээс хэтрэхгүй гэж ойлгоно.

Одоо Сэрэжа хичнээн дараалал туузан цааснууд дээр бичигдсэнийг мэдэхийг хүсжээ. Хариуг $1000000007$ $(10^{9}+7)$ тоонд хуваан үлдэгдлийг олно уу.

Оролт

Эхний мөрөнд бүхэл тоо $n$ $(1 ≤ n ≤ 10^{5})$ байна. Хоёр дахь мөрөнд $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{6})$ гэсэн $n$ ширхэг бүхэл тоонууд байна.

Гаралт

Хариуг $1000000007$ $(10^{9} + 7)$ тоонд хуваан хэвлэ.