You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

保山市举办茶叶品质评比大赛，有 $n$ 份茶叶样品参与评比。根据茶叶的香气、滋味、汤色等指标，每份样品 $i$ 的最高可评等级为 $b_i$ 级。评委会要求：

1. 每份样品的最终评定等级为一个非负整数。
2. 每份样品的最终评定等级必须互不相同（区分优劣）
3. 每份样品 $i$ 的最终评定等级不能超过其最高可评等级 $b_i$

请计算满足条件的等级评定方案数量。

输入格式

第一行：一个整数 $n$，表示茶叶样品数量

第二行：$n$ 个整数 $b_1, b_2, \ldots, b_n$，表示每份样品的最高可评等级

输出格式

输出满足条件的等级评定方案数，对 $10^9 + 7$ 取模

输入样例

4
1 3 2 3

输出样例

8

样例解释

8 种等级评定方案如下：

$[0, 1, 2, 3],$

$[0, 2, 1, 3],$

$[0, 3, 1, 2],$

$[0, 3, 2, 1],$

$[1, 0, 2, 3],$

$[1, 2, 0, 3],$

$[1, 3, 0, 2],$

$[1, 3, 2, 0]$.

每个方案中，四份样品的评定等级都互不相同，且不超过各自的最高可评等级。

数据范围

对于所有测试数据，保证：$1 \leq n \leq 2 \times 10^5$，$0 \leq b_i \leq 10^9$

• 特殊性质 A：所有 $b_i$ 的值都相等
• 特殊性质 B：对于$1 \leq i \leq j \leq n$ ，保证 $b_i \leq b_j$。