题目描述

给定一个长度为$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$取模。

样例输入 1

3 2
1
2
3
1 2
1 3

样例输出 1

6

有四种操作方式：

• 在第一次和第二次操作中都什么也不做。最终序列将是$1,2,3$，逆序数为$0$。
• 在第一次操作中什么也不做，在第二次操作中执行交换。最终序列将是$3,2,1$，逆序数为$3$。
• 在第一次操作中执行交换，在第二次操作中什么也不做。最终序列将是$2,1,3$，逆序数为$1$。
• 在第一次和第二次操作中都执行交换。最终序列将是$3,1,2$，逆序数为$2$。

这些逆序数的和为$0+3+1+2=6$。

样例输入 2

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

样例输出 2

36

样例输入 3

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

样例输出 3

425