VERY IMPORTANT NOTE TO ALL DEC COURSE 2022 PARTICIPANTS (due to delays in email communication): Elementary is gone, so Advanced has a diagnostic test (if you fail, no Dec Course). Syllabus of diagnostic is anything in these prerequisite notes, please review them at this link. Problemsets can be found at this link and under Contests (Collections).

You are given an integer sequence of length `N`: `A _{1},A_{2},...,A_{N}`. Let us perform

- 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

Here, the inversion number of a sequence `P _{1},P_{2},...,P_{M}` is the number of pairs of integers

`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 is given from Standard Input in the following format:

NQA_{1}:A_{N}X_{1}Y_{1}:X_{Q}Y_{Q}

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

3 2 1 2 3 1 2 1 3

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.

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

Subtask | Score |
---|---|

1 | 100 |

2 | 0 |