题目描述

小博有 $n$ 个蛋仔，现在为了方便识别它们，要给他们设定编号。每个蛋仔都有自己喜爱的数字 $a_i$，它只想被设定一个介于 1 和 $a_i$ 之间的序号（包括 1 和 $a_i$），并且不能与其他任何一个蛋仔的序号相同。

现在小博想知道一共有多少种设定序号的方法。

你只用输出答案对 $10^9+7$ 取余的结果即可。

输入格式

第一行：一个整数 $n$，表示蛋仔的数量。

第二行：$n$ 个整数 $a_1,a_2...a_i$，依次表示第 $i$ 个蛋仔喜爱的数字。

输出格式

一个整数，表示编号的方案总数。

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