E. Марк цуглуулагч Виталикт барьсан бэлэг

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

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

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

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

Өнөөдөр марк цуглуулагч Виталикын төрсөн өдөр. "Робин Бобин" тамганы дэлгүүрийн эзэн байнгын үйлчлүүлэгч Виталикдаа төрсөн өдрөөр нь бэлэг барихаар шийджээ.

Виталикын эхний худалдан авсан тамганы үнийн хамгийн их ерөнхий хуваагч нь 1-ээс их тохиолдолд түүнд дахин нэг тамга бэлэглэх аж. Энэ нь худалдан авч буй тамганы үнийн хамгийн их ерөнхий хуваагч, бэлэг болгон өгөх тамганы үнэ $1$-тэй тэнцүү тохиолдолд Виталикийг дэлгүүр баярлуулж чадна гэсэн үг юм.

Дэлгүүрийн менежерийн таниас хүсэж буй зүйл бол нийт хичнээн тохиолдолд Виталик сэтгэл ханамжтай байхыг тооцох юм. Ийм байх боломжит нөхцөл маш их учир нийт боломжийн тоог $10^{9} + 7$-д хувааж гарах үлдэгдлийг олох ёстой. Виталикийн авах тамганаас хамаарч нөхцөл өөрчлөгдөнө.

Оролт

Оролтын эхний мөрөнд дэлгүүрт байгаа $n$ ($2 ≤ n ≤ 5*10^{5}$) ширхэг тамганы тоог оруулна.

2 дахь мөрөнд 2 ≤ a_i ≤ 10^7 нөхцлийг хангах бүхэл тоон дараалал байна. $a$ нь $i$ - дэх тамганы үнийг илтгэнэ.

Гаралт

Нийт боломжийн тоог 10^9 + 7 тоонд хуваагаад гарсан үлдэгдлийг хэвлэ.

Орчуулсан: ERDENI

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

Оролт
3
2 3 2
Гаралт
5
Оролт
2
9 6
Гаралт
0

Тэмдэглэл

Эхний жишээн дэх боломжит нөхцөлүүд:

  • Виталик 1 дэх тамгыг худалдаж авахад дэлгүүр түүнд 2 дахь тамгыг бэлэг болгон өгнө.
  • Виталик 3 дахь тамгыг худалдаж авахад дэлгүүр түүнд 2 дахь тамгыг бэлэг болгон өгнө.
  • Виталик 2 дахь тамгыг худалдаж авахад дэлгүүр түүнд 1 дэх тамгыг бэлэг болгон өгнө.
  • Виталик 2 дахь тамгыг худалдаж авахад дэлгүүр түүнд 3 дахь тамгыг бэлэг болгон өгнө.
  • Виталик 2 дахь тамгыг худалдаж авахад дэлгүүр түүнд 1, 3 дахь тамгыг бэлэг болгон өгнө.
Сэтгэгдлүүдийг ачааллаж байна...