농부 존에게는 N마리의 소가 있다. 소들의 키는 다양하며, 두 마리의 소의 키가 서로 같을 수 있다.</p>

자신의 헤어스타일이 마음에 들지 않았던 소들은 일렬로 서서 서로의 헤어스타일을 확인해 주려고 한다.

각 소들은 자신의 오른쪽을 바라보면서 자신보다 키가 같거나 큰 소가 등장하기 전까지 나온 모든 소들의 헤어스타일을 확인할 수 있다. 더 정확하게는, 왼쪽에서 i번째에 서 있는 소의 키를 H'_i라 하면, i번째 소는 다음 조건을 만족할 때 (또한 그러할 때에만) j번째 소를 볼 수 있다.

• i < j고, H'_i > H'_j다.
• i < k < j고, H'_i ≤ H'_k를 만족하는 k가 존재하지 않는다.

소들이 N마리 있으므로, 그들이 일렬로 설 수 있는 방법은 총 N!가지다. 농부 존은 헤어스타일을 확인할 수 있는 소들 쌍의 수의 기댓값이 궁금해졌다. 농부 존을 도와, 이 기댓값을 출력하는 프로그램을 작성하시오.

입력 형식

첫 번째 줄에 소의 수를 나타내는 자연수 N이 주어진다.</p>

두번째 줄에 N마리의 소의 키를 나타내는 N개의 자연수 H₁, ···, H_N가 사이에 공백을 두고 주어진다.

출력 형식

어떤 서로소이고 음이 아닌 두 정수 $P$, $Q$가 존재하여, 헤어스타일을 확인할 수 있는 소들 쌍의 수의 기댓값이 $\displaystyle \frac{P}{Q}$와 같다고 하자. 이때, $P \equiv QX \pmod{10^{9} + 7}$를 만족하는 0 이상 (10⁹ + 7) 미만의 정수 $X$를 구하여 첫 번째 줄에 출력한다.</p>

조건을 만족하는 $P$, $Q$, $X$는 반드시 존재한다. 또한 $X$는 유일하게 존재함이 보장된다.

예제 입력 1

4
1 1 2 2

예제 출력 1

333333337

예제 입력 2

4
10 20 30 40

예제 출력 2

416666672