题目描述

给定一个长度为 $N$ 的整数序列 $A_1,A_2,\ldots,A_N$。你需要依次进行 $Q$ 次操作。第 $i$ 次操作由两个整数 $X_i,Y_i$ 给出，你可以从以下两种操作中恰好选择一种执行：

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

所有操作的执行方式共有 $2^Q$ 种。请你求出对于所有可能的操作方式，最终得到的序列的逆序对数之和，并对 $10^9+7$ 取模。

其中，序列 $P_1,P_2,\ldots,P_M$ 的逆序对数定义为满足 $1\leq i<j\leq M$ 且 $P_i>P_j$ 的整数对 $(i,j)$ 的个数。

输入格式

输入从标准输入读入，格式如下：

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$X_1$ $Y_1$
$\vdots$
$X_Q$ $Y_Q$

输出格式

输出所有可能的最终序列的逆序对数之和对 $10^9+7$ 取模的结果。

样例 1

输入

3 2
1
2
3
1 2
1 3

输出

6

样例 2

输入

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

输出

36

样例 3

输入

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

输出

425

说明/提示

限制条件

• $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)$
• 输入均为整数

样例说明 1

所有可能的操作方式如下，共有 $4$ 种：

• 第 $1$ 次和第 $2$ 次都什么都不做。最终序列为 $1,2,3$，逆序对数为 $0$。
• 第 $1$ 次什么都不做，第 $2$ 次交换。最终序列为 $3,2,1$，逆序对数为 $3$。
• 第 $1$ 次交换，第 $2$ 次什么都不做。最终序列为 $2,1,3$，逆序对数为 $1$。
• 第 $1$ 次和第 $2$ 次都交换。最终序列为 $3,1,2$，逆序对数为 $2$。

这几种情况下逆序对数之和为 $0+3+1+2=6$，输出 $6$。

由 ChatGPT 4.1 翻译