题目描述

小博有 n 个蛋仔，现在为了方便识别它们，要给他们设定 了它们对号码的喜好，每个蛋仔 i 想要一个整数，介于 1 和$a_i$序号。蛋仔们向小博表达i之间（包括 1 或$a_i$）。当然，每个蛋仔的序号是不同的。现在小博想知道一共有多少种设定序号的方法。你只用输出答案对$10^9+7$ 取余的结果即可。

输入格式

输入文件 number.in。 第一行，一个整数 n，表示蛋仔的数量。 第二行，n 个整数，其中第 i 个元素$a_i$表示第 i 个蛋仔喜好的号码范围。

输出格式

输出文件 number.out。 输出一个整数，表示号码的方案总数。

2
5 8

35

2
2 3

4

样例 2 解释

第一个蛋仔的序号是 1 时，第二个蛋仔有2，3 序号这两种方案。 第一个蛋仔的序号是 2 时，第二个蛋仔有1，3 序号这两种方案，共四种。

数据范围

10%的数据：满足 n=3，$1≤a_i≤10$。
另外 10%的数据：满足 n=5，$1≤a_i≤10$。
另外 10%的数据：满足 n=7，$1≤a_i≤10$。
另外 20%的数据：满足 $1≤n≤10^5，a_i和 n 相等$。
100%的数据：满足 $1≤n≤10 6，1≤a_i≤10^8$。