배열하고 세기!

Alice는 수열 $a_1,a_2,\dots,a_n$을 가지고 있다. 그녀는 다음 연산을 원하는 만큼 사용해 수열을 재배열할 수 있다:

• 정수 $i$ ($1 \le i \le n$)를 골라 수열을 $a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}$로 바꾼다.

Alice는 서로 다른 수열이 몇 개나 얻어질 수 있는지 알고 싶다. 답을 $(10^9+7)$로 나눈 나머지를 구하라.

입력은 여러 테스트 케이스로 이루어지며, 파일의 끝에서 끝난다. 각 테스트 케이스는 다음과 같다.

첫째 줄에는 수열의 길이 $n$이 주어진다.

둘째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$이 주어진다.

각 테스트 케이스마다 답을 나타내는 정수를 한 줄에 출력한다.

• $1 \leq n \leq 10^5$
• $1 \leq a_i \leq n$
• $n$의 합은 $2 \times 10^6$을 넘지 않는다.