시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 21 21 18 100.000%

문제

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

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

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

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

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

입력

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

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

출력

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

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

제한

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

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

예제 입력 1

4
1 1 2 2

예제 출력 1

333333337

첫번째 입출력 예제에서, 소들이 일렬로 설 수 있는 방법과 헤어스타일을 확인할 수 있는 소들 쌍의 수는 아래 표와 같다.

소들이 일렬로 선 방법 헤어스타일을 확인할 수 있는 소 쌍의 수
1, 1, 2, 2 0
1, 2, 1, 2 1
1, 2, 2, 1 1
2, 1, 1, 2 2
2, 1, 2, 1 2
2, 2, 1, 1 2

따라서 기댓값은 $\displaystyle \frac{0 + 1 + 1 + 2 + 2 + 2}{6} = \frac{4}{3}$다.

예제 입력 2

4
10 20 30 40

예제 출력 2

416666672

출처

High School > 경기과학고등학교 > 나는코더다 2019 송년대회 J번

  • 문제를 만든 사람: sebinkim
  • 데이터를 만든 사람: yclock