You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

olinr 是一个资深二刺螈，这一天，他进入了《冰菓》的世界

题目描述

olinr 在古典文学部见到了好奇宝宝千反田爱瑠

此时的千反田已经被一个问题困惑多时。在她的桌子上有一个不完整的格子纸，左上角的格子有一个数

字$1$ ，其他格子都是数字$0$ 。对于这张纸的格子，简单来说，总共有 $n+1$ 行，第i 行有$ai$ 列，保证

$a_{i+1}≤ a_i$

这个格子纸的背面写着玩法：对于格子上的数字，每次你可以让一个格子的数字减$1$ ， 让他右边和下边 相邻的格子（如果有的话）加$1$ 。求把所有格子变成0需要几步。

输入格式

第一行一个整数$n$

接下来一行 个数字，第 个数字代表$ai$

输出格式

输出答案对$10^9 + 7$ 取模的结果

输入样例1

5
3 2 1 1 1 1

输出样例1

10

输入样例2

4
4 2 2 2 2

输出样例2

22

数据范围

对于 $20\%$ 的数据 ，$n\le10$ 。

对于 $40\%$ 的数据 ，$n\le100$ 。

对于 $100\%$ 的数据 ，$n\le100000$ 。