시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 31 29 24 96.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