题目背景

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$ 。