암호학

암호학자 Charles는 난수를 생성하는 새로운 방법을 연구하고 있다. 특히 여러 난수 원천을 결합해 암호학적으로 안전한 의사난수 생성기(CSPRNG)를 만드는 것이 목표이다.

그가 최근에 고안한 알고리즘은 다음과 같다.

1. 서로 다른 N개의 양의 정수 S1, . . . , SN으로 이루어진 수열 S를 무작위로 생성한다.
2. S를 무작위로 섞어 N개의 원소로 이루어진 순열1 P1, . . . , PN을 얻는다.
3. P의 사전 순서를 구한다.
4. 답이 매우 클 수 있으므로 값을 1 000 000 007로 나눈 나머지2를 출력한다.

P의 사전 순서란 P보다 사전 순으로 작거나 같은3 S의 순열의 개수로 정의한다.

안타깝게도 Charles는 코더가 아니라 암호학자이다. 결과로 얻은 순열 P가 주어질 때, P의 사전 순서를 1 000 000 007로 나눈 나머지를 구해 Charles를 도와라.

1수열 S의 순열 P란 S의 원소를 재배열한 것이다.

2값을 1 000 000 007로 나누었을 때의 나머지

3순열 P1, . . . , PN이 다른 순열 P'1 , . . . , P'N보다 사전 순으로 작다는 것은 Pi = P'i (i = 1, . . . , k − 1)이면서 Pk < P'k인 1 ≤ k ≤ N이 존재한다는 뜻이다.

프로그램은 표준 입력에서 입력을 읽는다.

첫째 줄에 정수 N이 주어진다.

둘째 줄에 N개의 정수 P1, . . . , PN이 공백으로 구분되어 주어진다.

프로그램은 표준 출력에 출력을 쓴다. P의 사전 순서를 1 000 000 007로 나눈 나머지를 한 줄에 하나의 정수로 출력한다.

• 1 ≤ N ≤ 3 × 105
• 1 ≤ Pi ≤ 109
• Pi ≠ Pj (i ≠ j)