题目内容

小红是一个喜欢玩数字游戏的小朋友，他有一个神奇的魔法盒子，里面可以放任意多个数字卡片。每张卡片上都有一个正整数，小红可以随意拿出或放入卡片。有一天，小红拿到了一个数组，他想用魔法盒子来做一个游戏。他把数组中的每个元素都写在一张卡片上，然后按顺序放入魔法盒子。然后他开始按照以下规则操作：

1. 如果魔法盒子里的第一张卡片上的数字是 $0$ ，那么小红就把它扔掉，并把魔法盒子里剩下的所有卡片都向前移动一位，填补空缺。
2. 如果魔法盒子里的第一张卡片上的数字不是 $0$ ，假设是第一张卡片上的数字是 $a_0$ ，那么小红就在魔法盒子的最后面添加 $a_0$ 张卡片，每张卡片上的数字都是 $a_0−1$ ，然后把魔法盒子里第一张卡片上的数字减去 $1$ 。

小红每做一次操作，就会在纸上画一个小圈圈，表示自己很开心。他想知道，从开始进行操作直到魔法盒子里没有卡片了，他一共画了多少个小圈圈？由于小红很聪明，他知道如果结果可能很大，所以他会让结果对 $10^9+7$ 取模。

输入描述

第一行输入为一个正整数 $n$ ，代表数组的长度。

第二行输入为 $n$ 个正整数，第 $i$ 个数是 $a_i$ 代表数组的元素。

$1 \le n \le 10^5$ $1 \le a_i \le10^5$

输出描述

一个整数，代表操作的次数对 $10^9+7$ 取模的值。

样例1

输入

2
1 1

输出

6

样例解释 第一次操作， 数组变成 $[0,1,0]$

第二次操作，数组变成 $[1, 0]$

第三次操作，数组变成 $[0,0,0]$

第四次操作，数组变成 $[0,0]$

第五次操作，数组变成 $[0]$

第五次操作，数组变成 $[]$

样例2

输入

3
2 3 2

输出

61