很久以前,瓦西里在他的乡间别墅里建了一道很好的栅栏。瓦西里称栅栏是好的,如果它是一系列连续固定的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
注意
从第一个示例的栅栏中不可能精确地切割一块,因此剩余的栅栏是好的。
第二个示例中生成的栅栏的所有可能变体如下所示(灰色显示剪切部分):