inversionsum

inversionsum

Problem Statement

You are given an integer sequence of length N: A1,A2,...,AN. Let us perform Q operations in order. The i-th operation is described by two integers Xi and Yi. In this operation, we will choose one of the following two actions and perform it:

  • Swap the values of AXi and AYi
  • Do nothing

There are 2Q 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 109+7.

Here, the inversion number of a sequence P1,P2,...,PM is the number of pairs of integers (i,j) such that 1≤ i < j≤ M and Pi > Pj.

Constraints

  • 1 ≤ N ≤ 3000
  • 0 ≤ Q ≤ 3000
  • 0 ≤ Ai ≤ 109(1≤ i≤ N)
  • 1 ≤ Xi,Yi ≤ N(1≤ i≤ Q)
  • Xi≠ Yi(1≤ i≤ Q)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
A1
:
AN
X1 Y1
:
XQ YQ

Output

Print the sum of the inversion numbers of the final sequences, modulo 109+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

Submitting to 'inversionsum'


You're not logged in! Click here to login


Submitting to 'inversionsum'


You're not logged in! Click here to login


Submitting .cpp to 'inversionsum'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 3 Seconds
Memory Limit: 1024MB
No. of ACs: 1
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0