4389: D. 逆序对 (inverse.c/cpp/pas)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
Luke 发现人们的幸福感取决于一个长度为$n$的数字序列。
她有$m$个机会，每个机会都允许她交换序列中的两个数字，但也可以选择不交换。
一个人的幸福感由序列中的逆序对数量决定，其中一个逆序对是指满足$i < j \leq n$且$a_i > a_j$的数字对。
Luke 对于这$m$个机会的所有可能操作（每个机会都有选择交换或不交换的两种方式）非常好奇。
她想知道所有这些操作方式中，总的幸福感值之和是多少。由于这个值可能非常大，请你输出其对 $ 1000000007 $ 取模后的结果。
输入
### Input
第一行两个正整数 $n, m$。
接下来 $n$ 个数表示 $a_i$。
接下来 $m$ 个数对 $x,y$，第 $i$ 个数对表示这个操作可以交换 $a_x$ 和 $a_y$
输出
### Output
输出一行一个整数表示答案。
样例输入 复制
3 2
1 2 3
1 2
1 3样例输出 复制
6提示
### Examples
#### 【样例 1 输入】
```input
3 2
1 2 3
1 2
1 3
```
#### 【样例 1 输出】
```output
6
```
#### 【样例 1 解释】
抓住两个机会，最终序列为(3,1,2)，逆序对数量为 2
只抓住第一个机会，最终序列为(2,1,3)，逆序对数量为 1
只抓住第二个机会，最终序列为(3,2,1)，逆序对数量为 3
两个机会都不抓住，最终序列为(1,2,3)，逆序对数量为 0
2 + 1 + 3 + 0 = 6
#### 【样例 1 输入】
```input
3 2
1 2 3
1 2
1 3
```
#### 【样例 1 输出】
```output
6
```
#### 【样例 2 输入】
```input
95 97
8702 14726 30407 21093 26782 16683 25228 18234 8424 5672 9021 6769 27310 25820 20559 28660 23353 10811 31858 13060 1757 26391 11206 914 18640 6303 31308 4845 15677 6693 1691 13214 8595 21540 29908 8336 3875 23681 7639 16245 17386 27665 16055 25188 28075 19804 15468 19655 11074 10400 20424 32628 14388 20761 11693 4122 30346 30592 32636 4063 19168 26066 16336 17735 32441 10322 20333 15704 7445 18385 22131 30716 32070 31021 17880 13222 28671 26136 3348 7224 17070 29466 22558 24869 3339 9945 27032 30418 31985 5785 25926 1859 5230 31743 7877
59 92
40 72
76 83
6 40
92 88
41 50
59 41
69 23
50 29
5 86
33 78
51 81
33 88
37 13
19 53
66 91
92 63
43 10
7 76
68 37
10 27
27 92
82 74
15 2
10 25
72 34
2 13
44 76
10 60
75 69
40 33
12 4
30 40
82 21
3 82
57 10
47 67
22 43
91 54
74 24
3 14
59 5
62 83
15 77
61 35
1 10
86 77
61 60
46 67
20 17
37 13
70 12
30 95
81 15
12 74
75 10
84 36
74 18
85 34
38 84
9 32
64 3
13 49
70 62
72 85
87 35
78 77
66 81
12 85
66 9
25 59
78 39
74 24
71 85
31 80
94 58
41 57
81 2
61 25
95 70
91 1
1 89
81 56
73 89
79 59
69 38
28 61
36 35
95 44
93 43
50 11
11 79
54 87
56 61
65 36
12 70
16 2
```
#### 【样例 2 输出】
```output
909187410
```
### Notes
对于$20\%$的数据，$n, m \le 10$
对于$50\%$的数据，$n, m \le 100$
对于$100\%$的数据，$n, m \le 1000,0 \leq a_i \leq 10^9$