除了 CEOI 和冰球锦标赛外，捷克共和国今年还举办了卡尔文球（Calvinball）锦标赛。我们不去探讨卡尔文球那些近乎虚构的规则，而是专注于其队伍选择程序。

卡尔文球比赛由 $n$ 名名字各不相同的选手参加，他们被分成任意数量的非空队伍。为了记录队伍，采用以下约定：首先，每支队伍中名字字典序最小的选手被选为该队的队长。然后，各队按其队长的名字进行字典序排序，并从 1 开始用连续整数编号。最后，将所有选手按名字的字典序排列，并列出他们所属的队伍编号。

例如，如果有三支队伍，一支由 Calvin、Hobbes 和 Susie 组成，一支由 Tom 和 Jerry 组成，另一支仅由 Batman 组成，记录如下：

Batman 1 Calvin 2 Hobbes 2 Jerry 3 Susie 2 Tom 3

锦标赛每天由相同的选手参加，但每天选择的队伍组合不同。由于每天的选手相同，为了简洁起见，我们可以省略他们的名字，仅将队伍记录为队伍编号序列（在上述例子中为 1 2 2 3 2 3）。当所有可能的队伍选择方式都被尝试过后，锦标赛结束。

由于可能的队伍选择方式很多，决定每天的队伍组合曾经非常令人困惑。今年，国际卡尔文球组织决定，队伍选择将按照代表它们的序列的字典序进行。因此，第一天，所有选手都在同一支队伍中（序列 1 1 1 1 1 1），第二天除 Tom 外所有人都在同一队（序列 1 1 1 1 1 2），……，最后一天，每个人都各自为战（序列 1 2 3 4 5 6）。

对于给定的队伍记录，确定它将在锦标赛的第几天使用。输出该天数对 1 000 007 取模的结果。

请注意，示例中的选手名字仅用于解释，在实际任务中不起任何作用。

输入格式

从标准输入读取队伍描述。输入的第一行包含一个正整数 $n$ ($1 \le n \le 10\,000$)。输入的第二行包含 $n$ 个由空格分隔的正整数，给出任务描述中指定的队伍描述。

输出格式

向标准输出写入一个整数，表示给定队伍选择在锦标赛中使用的天数，结果对 1 000 007 取模。锦标赛的第一天编号为 1。

样例

样例输入 1

3
1 2 2

样例输出 1

4

说明

注意，3 人锦标赛中可能的队伍选择为 1 1 1；1 1 2；1 2 1；1 2 2；以及 1 2 3。

子任务

共有 10 组测试数据，每组 10 分。各组测试中 $n$ 的上限如下：

此外，第 4 组和第 8 组测试仅包含一个测试用例，其中描述队伍的序列为 1 2 3 ... n（即描述了锦标赛最后一天的情形，此时每个人都各自为战）。