F. Starlight
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

某地的地面上共有 $$$n$$$ 块石块堆成一列，从左到右第 $$$i$$$ 块的大小为 $$$a_i$$$，其中序列 $$$a$$$ 为一 $$$1 \sim n$$$ 的排列。小 H 打算将这 $$$n$$$ 块石块堆成一座高塔，并登上高塔，从而摘得星星。

在从第 $$$1$$$ 天开始的每天，小 H 将取出地面上所有石块中最靠左的一块，堆到高塔的顶部（最上方）。然而，若此时高塔顶部的石块的大小比高塔中任意一块其它石块要大，则高塔将倒塌，其中所有石块将按照等概率随机的顺序回到地面上石块序列的最左侧。否则，若高塔没有倒塌，且所有的 $$$n$$$ 块石块都在高塔中，则小 H 成功摘得星星。

现有 $$$q$$$ 次事件，在第 $$$i$$$ 次事件中，地面上第 $$$x$$$ 块石块和第 $$$y$$$ 块石块交换了位置。即，交换了序列 $$$a$$$ 中的 $$$a_x$$$ 和 $$$a_y$$$。请你设计程序，在一开始以及每次事件发生之后，计算出小 H 期望在第几天可以摘得星星。

可以证明答案是一个整数，请你输出答案对 $$$10^9 + 7$$$ 取模的结果。

Input

第一行两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \leq n, q \leq 2 \times 10^5)$$$，分别表示石块的数量，和需要处理的事件的个数。

接下来一行 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$，保证 $$$1 \leq a_i \leq n$$$ 且 $$$a_i$$$ 互不相同。换言之，$$$a$$$ 是一个 $$$1 \sim n$$$ 的排列。

接下来 $$$q$$$ 行，每行两个整数 $$$x$$$ 和 $$$y$$$ $$$(1 \leq x, y \leq n, x \neq y)$$$，表示在第 $$$i$$$ 次事件中，地面上第 $$$x$$$ 块石块和第 $$$y$$$ 块石块交换了位置。

Output

输出共 $$$q + 1$$$ 行。第一行表示在所有事件发生之前的答案。接下来对每次事件输出一行，表示该事件发生之后的答案。需要注意的是，事件之间不是相互独立的，每次事件交换之后序列 $$$a$$$ 不会复原。

Examples
Input
2 2
1 2
1 2
1 2
Output
6
2
6
Input
3 3
1 2 3
1 2
2 3
1 3
Output
22
18
7
22
Note

对于第一组样例，若石块序列为 $$$2, 1$$$，则小 H 必然可以在第 $$$2$$$ 天摘得星星。否则，若石块的序列为 $$$1, 2$$$，则高塔必然将在第二天倒塌，石块序列随机变为 $$$1,2$$$ 或 $$$2,1$$$ 之一。

若设小 H 在石块序列为 $$$1, 2$$$ 时，期望在第 $$$z$$$ 天可以摘得星星，则可以列出方程：$$$z = 2 + \frac{1}{2}(2 + z)$$$，可以解得 $$$z = 6$$$。

在一开始，石块序列为 $$$1, 2$$$，因此你输出 $$$6$$$。第一次事件发生之后，序列被交换为 $$$2, 1$$$，因此输出 $$$2$$$。第二次事件发生之后，序列又从 $$$2, 1$$$ 再次被交换成了 $$$1, 2$$$，因此输出 $$$6$$$。