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 java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ilyakor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        static final int mod = 1000 * 1000 * 1000 + 7;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int q = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt();
            }
            long[][] d = new long[n][n];
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    d[i][j] = (a[i] < a[j] ? 1 : 0);
            long inv2 = IntegerUtils.pow(2, mod - 2, mod);
            for (int it = 0; it < q; ++it) {
                int x = in.nextInt() - 1;
                int y = in.nextInt() - 1;
                Assert.assertTrue(x != y);
                for (int i = 0; i < n; ++i) {
                    if (i == x || i == y) continue;
                    d[i][x] = (((d[i][x] + d[i][y]) * inv2) % mod);
                    d[i][y] = d[i][x];
                    d[x][i] = (((d[x][i] + d[y][i]) * inv2) % mod);
                    d[y][i] = d[x][i];
                }
                long val = (d[x][y] + d[y][x]) * inv2;
                val %= mod;
                d[x][y] = val;
                d[y][x] = val;
            }
            long mult = IntegerUtils.pow(2, q, mod);
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j < n; ++j) {
//                System.err.print((d[i][j] * (long) mult) % mod + " ");
//            }
//            System.err.println();
//        }
//        System.err.flush();
            long res = 0;
            for (int i = 0; i < n; ++i)
                for (int j = i + 1; j < n; ++j) {
                    res += d[j][i];
                    res %= mod;
                }
//        for (int i = 0; i < 30; ++i)
//            System.err.println(i + ": " + (res * IntegerUtils.pow(2, i, mod)) % mod);
            res *= mult;
            res %= mod;
            out.printLine(res);
        }

    }

    static class IntegerUtils {
        public static int pow(long x, long y, int mod) {
            x %= mod;
            long res = 1;
            while (y > 0) {
                if (y % 2 == 1) {
                    --y;
                    res = (res * x) % mod;
                } else {
                    y /= 2;
                    x = (x * x) % mod;
                }
            }
            return (int) (res % mod);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buffer = new byte[10000];
        private int cur;
        private int count;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isSpace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (count == -1) {
                throw new InputMismatchException();
            }
            try {
                if (cur >= count) {
                    cur = 0;
                    count = stream.read(buffer);
                    if (count <= 0)
                        return -1;
                }
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            return buffer[cur++];
        }

        public int readSkipSpace() {
            int c;
            do {
                c = read();
            } while (isSpace(c));
            return c;
        }

        public int nextInt() {
            int sgn = 1;
            int c = readSkipSpace();
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = res * 10 + c - '0';
                c = read();
            } while (!isSpace(c));
            res *= sgn;
            return res;
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }

    static class Assert {
        public static void assertTrue(boolean flag) {
//        if (!flag)
//        while (true);
            if (!flag)
                throw new AssertionError();
        }

    }
}