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.

Background

小北和辰辰在玩扔石子游戏。

Description

小北给辰辰了 $n$ 个石子，每个石子都有它的大小 $a_i$。现在辰辰可以将其随意乱扔，即将石子打乱顺序，问有多少种打乱方案，使得打乱后石子大小单调递增（非严格），答案对 $10^9 + 7$ 取模。

注意：石子是本质不同的。

Format

Input

• 第 $1$ 行：$1$ 个整数 $n$；
• 第 $2$ 行：$n$ 个整数 $a_i$。

Output

• $1$ 个整数表示答案，对 $10^9 + 7$ 取模。

Samples

5
5 2 4 1 3

1

只有 $1, 2, 3, 4, 5$ 是单调递增的，因此答案为 $1$。

5
1 2 2 3 4

2

我们重新定义 $a_i$ 为一个二元组 $(a_i, i)$，则有两种合法方案：

• $(1, 1), (2, 2), (2, 3), (3, 4), (4, 5)$；
• $(1, 1), (2, 3), (2, 2), (3, 4), (4, 5)$。

因此答案为 $2$。

Limitation

• 对于 $20\%$ 的数据，$n \le 10$；
• 对于另外 $10\%$ 的数据，保证 $a_i$ 随机；
• 对于另外 $10\%$ 的数据，$a_i$ 两两相同；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。