20788번 - Arrange and Count! 다국어

문제

Alice has a sequence $a_1,a_2,\dots,a_n$. She can rearrange the sequence using the following operation any number of times:

• Select an integer $i$ (1ドル \le i \le n$) and change the sequence to $a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}$.

Alice would like to know the number of different sequences can be obtained modulo $(10^9+7)$.

입력

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains an integer $n,ドル the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

출력

For each test case, print an integer which denotes the result.

제한

• 1ドル \leq n \leq 10^5$
• 1ドル \leq a_i \leq n$
• The sum of $n$ does not exceed 2ドル \times 10^6$.

힌트