Танд нэгэн сэлгэмэл өгөгдөнө. Толь бичгийн дарааллаар энэхүү сэлгэмлээс хэтрэхгүй бүх сэлгэмэл дэх өөрчлөлтийн тоог тооцоолно уу.

Хариу нь маш том тоо болж магадгүй учир $1000000007 (10^9 + 7)$-д хуваасны үлдэгдлийг олно уу.

Оролт

Эхний мөрөнд сэлгэмлийн урт болох бүхэл тоо $n$ $(1\leq n \leq 10^6 )$ өгөгдөнө. Удаах мөрөнд $n$ ширхэг ялгаатай бүхэл тоо өгөгдөнө. $p_1,p_2, ... , p_n (1 \leq p_i \leq n)$

Гаралт

Бодлогын хариуг $1000000007 (10^9 + 7)$-д хуваасны үлдэгдэл болох нэгэн бүхэл тоог хэвлэнэ.

$n$ урттай сэлгэмэл гэдэг нь 1-ээс $n$ хүртлэх ялгаатай тооноос бүрдсэн n ширхэг тооны дараалал юм. $p_1, p_2, ..., p_n$ сэлгэмэл дэх өөрчлөлт гэдэг нь $i < j бөгөөд p_i > p_j$ байх $(i,j)$ хос индексийг хэлнэ.

Сэлгэмэл $a$ болон $b$-н хувьд $(a=b)$ эсвэл $(\forall j