Description

给 $n$ 个点染色，每个点都需要一种独一无二的颜色。颜色以数字编号，每个点对颜色都有各自的要求。其中第 $i$ 个点要求颜色的编号为 $1$ 到 $a_i$之间的整数。

请统计有多少种染色方案数满足要求，由于答案可能很大，输出模 $10^9 + 7$的余数。

Format

Input

第一行：单个整数表示 $n$

第二行：$n$ 个整数表示 $a_1, a_2, \dots, a_n$

Output

单个整数表示答案

Samples

样例输入

3
4 7 2

样例输出

30

Limitation

$30\%$ 的数据，$1 \leq n \leq 10, 1 \leq a_i \leq 10$

$60\%$ 的数据，$1 \leq n \leq 100, 1 \leq a_i \leq 100$

$100\%$ 的数据，$1 \leq n \leq 300000, 1 \leq a_i \leq 10^9$