题目描述

对于一个非负整数序列 $A$，定义 $MEX(A)$ 为最小的不在 $A$ 中出现的非负整数。

现在给定非负整数序列 $B_1,B_2,\cdots,B_n$，求所有满足 $0\le A_i\le B_i~(i=1,\cdots,n)$ 的非负整数序列 $A$ 的 $MEX(A)$ 之和，答案对 $10^9+7$ 取模。

输入格式

第一行：一个正整数 $n$。

第二行：$n$ 个整数 $B_1,B_2,\cdots,B_n$。

输出格式

一个整数，表示答案。

样例输入1

5
6 8 3 2 1

样例输出1

2824

样例输入2

8
3 7 1 11 0 4 1 9

样例输出2

208746

数据范围

对于所有数据，满足 $1\le n\le 5000$，$0\le B_i\le 10^9$。