题目描述

Luke 发现人们的幸福感取决于一个长度为$n$的数字序列。

她有$m$个机会，每个机会都允许她交换序列中的两个数字，但也可以选择不交换。

一个人的幸福感由序列中的逆序对数量决定，其中一个逆序对是指满足$i < j \leq n$且$a_i > a_j$的数字对。

Luke 对于这$m$个机会的所有可能操作（每个机会都有选择交换或不交换的两种方式）非常好奇。

她想知道所有这些操作方式中，总的幸福感值之和是多少。由于这个值可能非常大，请你输出其对 $1000000007$ 取模后的结果。

输入格式

第一行两个正整数 $n, m$。

接下来 $n$ 个数表示 $a_i$。

接下来 $m$ 个数对 $x,y$，第 $i$ 个数对表示这个操作可以交换 $a_x$ 和 $a_y$

输出格式

输出一行一个整数表示答案。

样例输入 #1

3 2
1 2 3
1 2
1 3

样例输出 #1

6

数据范围

【样例 1 解释】

抓住两个机会，最终序列为(3,1,2)，逆序对数量为 2

只抓住第一个机会，最终序列为(2,1,3)，逆序对数量为 1

只抓住第二个机会，最终序列为(3,2,1)，逆序对数量为 3

两个机会都不抓住，最终序列为(1,2,3)，逆序对数量为 0

2 + 1 + 3 + 0 = 6

对于$20\%$的数据，$n, m \le 10$

对于$50\%$的数据，$n, m \le 100$

对于$100\%$的数据，$n, m \le 1000,0 \leq a_i \leq 10^9$