33OJ
登录 注册

#P17707. [ICPC 2019 Nanjing R] Space Station

    ID: 20159 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>暴力数据结构2019记忆化搜索ICPCAd-hoc南京

[ICPC 2019 Nanjing R] Space Station

Problem Description

There are n+1n+1 space stations in Penguin Galaxy, numbered from 00 to nn. The ii-th one has so-called energy of amount aia_i.

When you arrive at a station, you can gain all the energy in this station. Now, you are staying at the 00-th station, and you have already got the energy in this station of amount a0a_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 109+710^9+7.

Input Format

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

The second line contains n+1n+1 integers a0,a1,a2,⋯ ,an−1a_0, a_1, a_2, \cdots, a_{n-1} and ana_n where 0≤ai≤500 \le a_i \le 50 for i∈{0,1,2,⋯ ,n}i \in \{0, 1, 2, \cdots, n\}.

Output Format

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

3
2 1 2 3
4
5
1 1 1 1 2 3
54

Hint

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