Description

Taro has $N$ rabbits. To make them easier to identify, Taro will assign them numbers. The rabbits expressed their preferences: each rabbit $i$ wants an integer between $1$ and $M_i$ (it can be $1$ or $M_i$). Of course, the numbers assigned to different rabbits must be distinct. Now Taro wants to know how many ways there are to assign the numbers.

You only need to output the answer modulo $10^9+7$. If this is impossible, output $0$.

Input Format

The first line contains an integer $N$. The second line contains $N$ integers $M_i$.

Output Format

Print a single integer, the total number of ways.

2
5 8

35

Hint

Constraints

For all testdata, $1 \le N \le 50$, $1\le M_i\le 1000$.

Translated by ChatGPT 5