409246: GYM103466 I Space Station

There are $$$n+1$$$ space stations in Penguin Galaxy, numbered from $$$0$$$ to $$$n$$$. The $$$i$$$-th one has so-called energy of amount $$$a_i$$$.

When you arrive at a station, you can gain all the energy in this station. Now, you are staying at the $$$0$$$-th station, and you have already got the energy in this station of amount $$$a_0$$$. You will only be allowed to move to a station whose energy is less than or equal to what you've got at each time, and the movement between stations will cost you nothing, which can be ignored in computation.

Now, you decide to visit each station exactly once. How many different plans do you have to complete your trip? Since the answer will be pretty large, you just need to find the number module $$$10^9+7$$$.

The first line contains a single integer $$$n~(1\le n\le 10^5)$$$.

The second line contains $$$n+1$$$ integers $$$a_0,a_1,a_2,\cdots,a_n~(0\le a_i\le 50)$$$.

The output contains a single integer in a line indicating the number of different plans to complete your trip visiting all stations modulo $$$10^9+7$$$.

3
2 1 2 3

4

5
1 1 1 1 2 3

54

In the first example, the visiting order can be one of [0,1,2,3], [0,1,3,2], [0,2,1,3] and [0,2,3,1]. However, it cannot be [0,3,1,2] or [0,3,2,1]. Indeed when you start from the $$$0$$$-th station, you have gained only $$$2$$$ units of energy. Then you are not allowe to jump to the $$$3$$$-th statio since the energy there is $$$3$$$ which is bigger than what you hold.