得分 : $1000$ 分

问题陈述

给定一个长度为 $N$ 的整数序列：$A_1,A_2,...,A_N$。让我们依次执行 $Q$ 次操作。
第 $i$ 次操作由两个整数 $X_i$ 和 $Y_i$ 描述。在该操作中，我们将选择以下两个操作中的一个并执行：

• 交换 $A_{X_i}$ 和 $A_{Y_i}$ 的值
• 什么也不做

共有 $2^Q$ 种执行这些操作的方法。找出所有这些执行操作的方法的最终序列的逆序数之和，结果对 $10^9+7$ 取模。

这里，序列 $P_1,P_2,...,P_M$ 的逆序数是满足 $1\leq i < j\leq M$ 且 $P_i > P_j$ 的整数对 $(i,j)$ 的数量。

约束条件

• $1 \leq N \leq 3000$
• $0 \leq Q \leq 3000$
• $0 \leq A_i \leq 10^9(1\leq i\leq N)$
• $1 \leq X_i,Y_i \leq N(1\leq i\leq Q)$
• $X_i\neq Y_i(1\leq i\leq Q)$
• 所有输入值均为整数。

输入

输入从标准输入以以下格式给出：

$N$ $Q$

$A_1$

$:$

$A_N$

$X_1$ $Y_1$

$:$

$X_Q$ $Y_Q$

输出

打印最终序列的逆序数之和，结果对 $10^9+7$ 取模。

3 2
1
2
3
1 2
1 3

6

有四种执行操作的方法，如下所示：

• 什么也不做，第一和第二次操作均如此。最终序列为 $1,2,3$，逆序数为 $0$。
• 第一次操作不做，第二次进行交换。最终序列为 $3,2,1$，逆序数为 $3$。
• 第一次操作进行交换，第二次不做。最终序列为 $2,1,3$，逆序数为 $1$。
• 两次操作均进行交换。最终序列为 $3,1,2$，逆序数为 $2$。

这些逆序数的和为 $0+3+1+2=6$，应打印该结果。

5 3
3
2
3
1
4
1 5
2 3
4 2

36

9 5
3
1
4
1
5
9
2
6
5
3 5
8 9
7 9
3 2
3 8

425