Lịch sử cực đại

Cho một mảng $a$ gồm $n$ phần tử. Với một cách sắp xếp (hoán vị) cụ thể của mảng, ta định nghĩa giá trị $f_a$ như sau:

• Ban đầu $f_a=0$ và $M=1$.
• Với mỗi $i$ từ $2$ đến $n$: nếu $a_M<a_i$ thì gán $f_a=f_a+a_M$, sau đó gán $M=i$.

Nói cách khác, ta duyệt mảng từ trái sang phải và giữ vị trí $M$ của phần tử lớn nhất gặp được cho tới hiện tại. Mỗi khi gặp một phần tử lớn hơn hẳn phần tử đang giữ, ta cộng giá trị phần tử đang giữ vào $f_a$ rồi chuyển sang giữ phần tử mới.

Hãy tính tổng của $f_a$ trên tất cả $n!$ hoán vị của mảng, lấy phần dư khi chia cho ${10}^9+7$.

Hai phần tử được coi là khác nhau nếu chỉ số của chúng khác nhau, nên với mỗi mảng luôn có đúng $n!$ hoán vị (kể cả khi có các phần tử bằng nhau về giá trị).

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số phần tử của mảng.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất: tổng $f_a$ trên tất cả $n!$ hoán vị, lấy dư cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^6$
• $1\le a_i\le {10}^9$

Ví dụ