该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小丑在某个地方安了一个炸弹，需要输入正确的密码才能解除，而他已经把得到密码的方式告诉了蝙蝠侠。
众所周知，\(n\)阶全排列共有\(n!\)个，求出它们中所有字典序小于等于给定排列的排列逆序对数目之和，就是密码。

Format

Input

每个测试点仅有一组测试数据。
第一行一个整数\(n(1<=n<=10^6)\)，表示排列长度。
接下来\(n\)行，每行一个整数，第\(i\)行的数表示给定排列的第\(i\)个数\(a_i\)。
保证输入数据是一个排列。

Output

输出一行一个整数，为答案除以\(10^9+7\)所得余数。

Sample 1

Input

3
2
1
3

Output

2

Sample 2

Input

见附加文件中inversion.in。

Output

见附加文件中inversion.out。

Subtask

子任务1（10分）：\(n<=10\)。
子任务2（20分）：\(a_i=n-i+1\)。
子任务3（30分）：\(n<=2000\)。
子任务4（40分）：无附加限制。

Limitation

2s, 1GB for each test case.

Source

Vijos Original