Bad Hair Day와 기댓값

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

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

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

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

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

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

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

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

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

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 2 × 105
• 1 ≤ Hi ≤ 109 (1 ≤ i ≤ N)