問題文

長さ N の順列 P = p_1, p_2, ..., p_N が与えられます。長さ N の順列であって、P より辞書順で小さいか等しいもの全てについて転倒数を求め、その和を答えてください。ただし答えはとても大きくなることがあるので、10^9 + 7 で割った余りを出力してください。

ただし、順列 X = x_1, x_2, ..., x_N の転倒数とは、1 \leq i < j \leq N かつ x_i > x_j を満たす整数 i, j の組の個数のことです。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq p_i \leq N
• 入力は全て整数である。
• p_1, p_2, ..., p_N は順列である。

入力例1

3
2 1 3

出力例1

2

順列 (2, 1, 3) より辞書順で小さいか等しい、長さ 3 の順列は (1, 2, 3), (1, 3, 2), (2, 1, 3) の 3 種類です。

これらの順列の転倒数はそれぞれ 0, 1, 1 なので、答えは 0 + 1 + 1 = 2 となります。

入力例2

4
1 2 3 4

出力例2

0

入力例3

8
5 6 2 7 1 3 8 4

出力例3

281881