Erasing Game

Time limit1sMemory limit128 MB

Summary

Count the ordered sequences A whose entries can each be matched to a distinct entry of S that is at least as large.

Level: Medium7 of 10
Topics: Combinatorics, Sorting, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Hongjun and Myungwoo play a game with sequences. Hongjun first writes down a sequence $A$ of $N$ natural numbers, chosen however he likes, and Myungwoo writes down a sequence $S$ of the same length in the same way.

The game runs for $N$ rounds. In round $i$ , Hongjun has to erase one number from his own sequence $A$ that is not greater than $S_i$ . If no such number is left, Hongjun loses. If he finishes all $N$ rounds, Hongjun wins.

Given Myungwoo's sequence $S$ , count the sequences $A$ that let Hongjun win when he plays with an optimal strategy. Two sequences with the same numbers in a different order count as different sequences.

Input

The first line contains the length $N$ . ( $1 \le N \le 200$ )

The $i$ -th of the next $N$ lines contains $S_i$ . ( $1 \le S_i \le 10^9$ )

Output

Print the number of sequences $A$ that Hongjun can win with, modulo 1,000,000,007.

Hint

For $N = 2$ and $S = (1, 2)$ , the sequences $A$ that Hongjun can win with are $(1, 1)$ , $(1, 2)$ , and $(2, 1)$ .

Examples1

Example 1
Input
```
2
1
2
```
Expected output
```
3
```