题目描述

長さ $N$ の整数列 $A_1,A_2,...,A_N$ が与えられます。$Q$ 回の操作を順に行います。 $i$ 回目の操作は $2$ つの整数 $X_i,Y_i$ を用いて表され、以下の $2$ つの操作からちょうど片方を選んで行います。

• $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)$ の個数です。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $A_1$ $:$ $A_N$ $X_1$ $Y_1$ $:$ $X_Q$ $Y_Q$

输出格式

最終的な数列の反転数の総和を $10^9+7$ で割ったあまりを出力せよ。

题目大意

给你一个长度为 $n$ 的数列，然后给你 $q$ 个交换或不交换操作，你可以选择操作或者不操作，问所有情况下逆序对的总和。

答案需要对 $10 ^ 9 + 7$ 取模。

$n\leq 3000$，$q\leq 3000$。

3 2
1
2
3
1 2
1 3

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

提示

制約

• $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)$
• 入力はすべて整数である

Sample Explanation 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$ を出力します。