配点 : $1000$ 点

問題文

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

制約

• $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

操作の行い方としてありうるものは次の $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$ を出力します。

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