Max History

길이가 n인 배열 a가 주어진다. fa을 다음과 같이 정의한다.

• 처음에 fa = 0, M = 1이다;
• 모든 2 ≤ i ≤ n에 대해, aM < ai이면 fa = fa + aM로 설정한 다음 M = i로 설정한다.

배열 a의 모든 n!개 순열에 대한 fa의 합을 109 + 7로 나눈 나머지를 계산한다.

참고: 두 원소의 인덱스가 다르면 서로 다른 원소로 간주하므로, 모든 배열 a에는 정확히 n!개의 순열이 있다.

첫 번째 줄에는 배열 a의 크기인 정수 n (1 ≤ n ≤ 1 000 000)가 주어진다.

두 번째 줄에는 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 109)가 주어진다.

배열 a의 모든 n!개 순열에 대한 fa의 합을 109 + 7로 나눈 나머지인 유일한 정수를 출력한다.

두 번째 예제의 모든 순열은 다음과 같다.

• $p = [1, 2, 3]$ : fa은 1이다;
• $p = [1, 3, 2]$ : fa은 1이다;
• $p = [2, 1, 3]$ : fa은 1이다;
• $p = [2, 3, 1]$ : fa은 1이다;
• $p = [3, 1, 2]$ : fa은 0이다;
• $p = [3, 2, 1]$ : fa은 0이다.

여기서 p은 초기 배열 a의 인덱스로 이루어진 배열이다. fa의 합은 4이다.