小丑的炸弹

小丑的炸弹

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

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

概率计数大狂欢

未参加
状态
已结束
规则
ACM/ICPC
题目
2
开始于
2019-08-10 14:00
结束于
2019-08-10 17:00
持续时间
3.0 小时
主持人
参赛人数
20