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