#1174. 渡渡鸟玩游戏

渡渡鸟发明了一种天才的游戏！可是它想知道这个游戏是否公平，以及有多么不公平。游戏规则是这样的：

假设 Alice 和 Bob 在玩游戏，首先他们会得到一个长度为 $n$ 的序列 $a_1 , a_2 , \cdots , a_n$ ，然后他们会随机生成一个长度为 $n$ 的 $[1,n]$ 的排列 $p_1 , p_2 ,\cdots , p_n$ ,定义这个排列的分数为 $\displaystyle\prod_{i=1}^n a_i^{p_i-1}$ ，之后找来了 Carl 来分配这个分数。

Carl 将进行若干次操作，每次操作交换这个排列的某相邻两项，直到其变为升序为止。如果交换需要的最小次数为偶数，分数给 Alice，否则给 Bob。

渡渡鸟想知道，对于一次游戏，Alice 的分数减 Bob 的分数的期望是多少。由于一些原因，你只需要输出期望乘 $n!$ 后模 $10^9 + 7$ 的结果即可。由于一共只有 $n!$ 种可能的游戏状态，所以答案一定会是整数。

第一行一个正整数 $n$，表示排列长度 ($2\leq n\leq 2000$)。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，含义如题目所描述。（$0\leq a_i< 10^9+7$）

仅一个非负整数，表示答案。

样例输入1

3
2 3 4

样例输出1

2

样例输入2

3
2 3 3

样例输出2

0

行列式的组合定义