← 返回题目列表

Codeforces · 659/G

G. 栅栏多样性

中文机器翻译题面 查看原题

很久以前,瓦西里在他的乡间别墅里建了一道很好的栅栏。瓦西里称栅栏是好的,如果它是一系列连续固定的n块厘米宽的垂直木板,那么每块木板的高度(以厘米为单位)都是正整数。房主记得左边第i块木板的高度是hi。

今天瓦西里决定改变他建造的栅栏的设计,通过切割他的顶部连接部分,使栅栏保持完好。切割部分应仅由木板的上部组成,而相邻部分必须互连(在切出栅栏之前共享非零长度)。

作为瓦西里好奇的邻居,您将计算出如上所述精确切割一个零件的可能方法的数量。如果对于剩余的栅栏存在这样的 i ,即第 i 块板的高度不同,则切割一个部分的两种方法被称为不同的。

由于瓦西里的栅栏可能非常高和长,因此将所需的路数除以 1 000 000 007 (109 + 7) 后得到余数。

输入

第一行包含整数 n (1 ≤ n ≤ 1 000 000) — Vasily 围栏中的木板数量。

第二行包含 n 个空格分隔的数字 h1, h2, ..., hn (1 ≤ hi ≤ 109),其中 hi 等于左侧第 i 个板的高度。

输出

打印 r 除以 1 000 000 007 后的余数,其中 r 是精确切割一个连接部分的方法数,以使该部分由木板的上部组成,剩余的围栏完好。

示例

输入 #1

2
1 1

输出 #1

0

输入 #2

3
3 4 2

输出 #2

13

注意

从第一个示例的栅栏中不可能精确地切割一块,因此剩余的栅栏是好的。

第二个示例中生成的栅栏的所有可能变体如下所示(灰色显示剪切部分):