G. Хашааны өвөрмөц шинж

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Удаан хугацааны өмнө, Васили өөрийн хөдөөний байшиндаа нэгэн сайн хашаа барьжээ. Хэрэв хашаа нь сантиметрийн өргөнтэй $n$ ширхэг дараалсан бэхэлсэн босоо хавтангуудын дараалал байвал Васили үүнийг сайн хашаа гэх ба хавтан тус бүрийн өндөр нь эерэг бүхэл тоон сантиметр байна. Байшингийн эзэн зүүнээсээ $i$-дахь хавтангийн өндөр нь $h_{i}$ гэдгийг санаж байв.

Өнөөдөр Васили хашаа нь сайн хэвээр байхаар дээд талын холбогдсон хэсгийг тайрах замаар өөрийн барьсан хашааныхаа загварыг өөрчлөхөөр шийджээ. Тайрах хэсэг нь зөвхөн хавтангуудын дээд хэсгээс тогтох ба зэргэлдээ хэсгүүд нь заавал холбогдсон байна (хашааг тайрахаас өмнө хэсгүүд нь нийтдээ 0-ээс ялгаатай урттай байна )

Та Васили-ын сониуч хөрш ба дээр дүрслэгдсэн шиг яг нэг хэсгийг тайрах хэчнээн боломжит арга байгааг тоолох юм. Хэрэв үлдсэн хашааны хувьд $i$-дахь хавтангуудын өндөр нь ялгаатай байх $i$ байвал нэг хэсэг тайрах уг 2 аргыг ялгаатай гэж үзнэ.

Васили-ын хашаа маш өндөр ба урт байж болох учраас, шаардлагатай аргын тоог $1 000 000 007$ $(10^{9} + 7)$-д хуваасны дараах үлдэгдлийг олно уу.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 1 000 000$) өгөгдөнө -- энэ нь Васили-ын хашааны хавтангуудын тоог илэрхийлнэ.

2-дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо $h_{1}, h_{2}, ..., h_{n}$ ($1 ≤ h_{i} ≤ 10^{9}$) өгөгдөх ба энд $h_{i}$ нь зүүнээсээ $i$-дахь хавтангийн өндөртэй тэнцүү байна.

Гаралт

$r$-г $1 000 000 007$-д хуваасны дараах үлдэгдлийг хэвлэх ба энд $r$ нь үлдэх хашаа нь сайн байх бөгөөд хавтангуудын дээд хэсгээс тогтох яг нэг холбогдсон хэсгийг тайрах аргын тоог илэрхийлнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2
1 1
Гаралт
0
Оролт
3
3 4 2
Гаралт
13

Тэмдэглэл

Эхний жишээний хашааны хувьд үлдэх хашаа нь сайн байхаар яг нэг хэсгийг тайрна гэдэг нь боломжгүй юм.

2-дахь жишээний үр дүнгийн хашааны бүх боломжит хувилбарууд нь дараах байдлаар харагдана (саарал хэсэг нь тайрагдсан хэсгийг дүрсэлнэ):

Сэтгэгдлүүдийг ачааллаж байна...