Problem: You are given an integer sequence of length N: A_1,A_2,...,A_N. Let us perform Q operations in order. The i-th operation is described by two integers X_i and Y_i. In this operation, we will choose one of the following two actions and perform it:

* Swap the values of A_{X_i} and A_{Y_i}
* Do nothing



There are 2^Q ways to perform these operations. Find the sum of the inversion numbers of the final sequences for all of these ways to perform operations, modulo 10^9+7.

Here, the inversion number of a sequence P_1,P_2,...,P_M is the number of pairs of integers (i,j) such that 1\leq i < j\leq M and P_i > P_j.

Constraints

* 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)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
A_1
:
A_N
X_1 Y_1
:
X_Q Y_Q


Output

Print the sum of the inversion numbers of the final sequences, modulo 10^9+7.

Examples

Input

3 2
1
2
3
1 2
1 3


Output

6


Input

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


Output

36


Input

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


Output

425

Solution (in PYTHON3):

Solution:
import sys
readline = sys.stdin.readline

MOD = 10**9+7
N, Q = map(int, readline().split())
A = [int(readline()) for _ in range(N)]

dp = [[0]*N for _ in range(N)]

tinv = pow(2, MOD-2, MOD)
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            dp[i][j] = 1

for q in range(Q):
    x, y = map(int, readline().split())
    x -= 1
    y -= 1
    dxy = dp[x][y]
    dyx = dp[y][x]
    ix = [None]*N
    iy = [None]*N
    xi = [None]*N
    yi = [None]*N
    for i in range(N):
        r1 = (dp[i][x] + dp[i][y])*tinv%MOD
        ix[i] = r1
        iy[i] = r1
        r2 = (dp[x][i] + dp[y][i])*tinv%MOD
        xi[i] = r2
        yi[i] = r2
    for i in range(N):
        dp[x][i] = xi[i]
        dp[y][i] = yi[i]
        dp[i][x] = ix[i]
        dp[i][y] = iy[i]
    dp[x][y] = (dxy + dyx)*tinv%MOD
    dp[y][x] = dp[x][y]
    dp[x][x] = 0
    dp[y][y] = 0

res = 0
for i in range(N):
    for j in range(i+1, N):
        res = (res+dp[i][j])%MOD
print(res*pow(2, Q, MOD)%MOD)