#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### inversionsum

### Problem Statement

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`and

_{i}`Y`. In this operation, we will choose one of the following two actions and perform it:

_{i}- Swap the values of
`A`and_{Xi}`A`_{Yi} - 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}+7Here, the inversion number of a sequence `P _{1},P_{2},...,P_{M}` is the number of pairs of integers

`(i,j)`such that

`1≤ i < j≤ M`and

`P`.

_{i}> P_{j}### Constraints

`1 ≤ N ≤ 3000``0 ≤ Q ≤ 3000``0 ≤ A`_{i}≤ 10^{9}(1≤ i≤ N)`1 ≤ X`_{i},Y_{i}≤ N(1≤ i≤ Q)`X`_{i}≠ Y_{i}(1≤ i≤ Q)- All values in input are integers.

### Input

Input is given from Standard Input in the following format:

NQA_{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`.

### Sample Input 1

3 2 1 2 3 1 2 1 3

### Sample Output 1

6

There are four ways to perform operations, as follows:

- Do nothing, both in the first and second operations. The final sequence would be
`1,2,3`, with the inversion number of`0`. - Do nothing in the first operation, then perform the swap in the second. The final sequence would be
`3,2,1`, with the inversion number of`3`. - Perform the swap in the first operation, then do nothing in the second. The final sequence would be
`2,1,3`, with the inversion number of`1`. - Perform the swap, both in the first and second operations. The final sequence would be
`3,1,2`, with the inversion number of`2`.

The sum of these inversion numbers, `0+3+1+2=6`, should be printed.

### Sample Input 2

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

### Sample Output 2

36

### Sample Input 3

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

### Sample Output 3

425

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 39 | 3s | 256MB | Minimum |

2 | 0 | 3 | 3s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o inversionsum -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512