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$.