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 JAVA):

Solution:
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static final int MOD = 1000000007;
	static final int HALF = (MOD + 1) / 2;

	static int add(int a, int b) {
		int res = a + b;
		return res >= MOD ? res - MOD : res;
	}

	static int mul(int a, int b) {
		int res = (int) ((long) a * b % MOD);
		return res < 0 ? res + MOD : res;
	}

	static void solve() throws Exception {
		int n = scanInt();
		int q = scanInt();
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = scanInt();
		}
		int v[][] = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				v[i][j] = a[i] < a[j] ? 1 : 0;
			}
		}
		for (int qq = 0; qq < q; qq++) {
			int x = scanInt() - 1;
			int y = scanInt() - 1;
			for (int i = 0; i < n; i++) {
				if (i != x && i != y) {
					v[i][x] = v[i][y] = mul(v[i][x] + v[i][y], HALF);
					v[x][i] = v[y][i] = mul(v[x][i] + v[y][i], HALF);
				}
			}
			v[x][y] = v[y][x] = mul(v[x][y] + v[y][x], HALF);
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				ans = add(ans, v[i][j]);
			}
		}
		for (int i = 0; i < q; i++) {
			ans = add(ans, ans);
		}
		out.print(ans);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}