在企鹅星系中有 $n+1$ 个空间站，编号从 $0$ 到 $n$。第 $i$ 个空间站拥有能量 $a_i$。

当你到达一个空间站时，你可以获得该空间站所有的能量。现在，你正处于第 $0$ 号空间站，并且已经获得了该空间站的能量 $a_0$。你每次只能移动到能量小于或等于你当前所持能量的空间站，且空间站之间的移动不需要消耗能量，在计算中可以忽略。

现在，你决定访问每一个空间站恰好一次。请问你有多少种不同的方案来完成你的旅行？由于答案可能非常大，你只需要输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

第二行包含 $n+1$ 个整数 $a_0, a_1, a_2, \dots, a_n$ ($0 \le a_i \le 50$)。

输出格式

输出一行，包含一个整数，表示访问所有空间站的方案数对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3
2 1 2 3

样例输出 1

4

样例输入 2

5
1 1 1 1 2 3

样例输出 2

54

说明

在第一个样例中，访问顺序可以是 $[0,1,2,3]$、$[0,1,3,2]$、$[0,2,1,3]$ 和 $[0,2,3,1]$。然而，它不能是 $[0,3,1,2]$ 或 $[0,3,2,1]$。事实上，当你从第 $0$ 号空间站出发时，你只获得了 $2$ 单位的能量。之后你不能跳到第 $3$ 号空间站，因为那里的能量为 $3$，大于你所持有的能量。