1616. Permutations

Professor Danko teaches maths at the university. This semester `N` students attend his lectures in discrete mathematics and combinatorics. On his last lecture Danko spoke about ranks of permutations.

A sequence of `K` integers between `1` and `K` such that each number occurs in a sequence exactly once is called a permutation. A permutation can be rearranged into total of `K`! different sequences. For example a sequence (1, 2, 3) can be rearranged in 3! = 6 ways. Permutations can be ordered into a sequence of permutations by comparing first elements, than second elements, then third, and so on.

1. (1, 2, 3)

2. (1, 3, 2)

3. (2, 1, 3)

4. (2, 3, 1)

5. (3, 1, 2)

6. (3, 2, 1)

The index of a permutation in a sequence of permutations is called the rank of permutation. For example, the rank of permutation (3, 1, 2) is 5.

Danko assigned a permutation to each of his students. Each student has to calculate the rank of given permutation. Danko used this simple algorithm to generate permutations:

He picked one base permutation of `K` integers. A permutation for each of his student is obtained from base permutation by swapping two elements.

Danko's assistant Janko must give grades to students. Professor gave him the base permutation and a sequence of `N` pairs of indices that should be swapped to obtain each permutation. For example, if the base permutation were (1, 5, 4, 2, 3), and pairs of indices were (1, 3), (2, 3) and (2, 5), then students got these three permutations: (4, 5, 1, 2, 3), (1, 4, 5, 2, 3) and (1, 3, 4, 2, 5). The ranks of permutations are 91, 17 and 9, respectively.

Write a program that will help Janko to calculate the ranks of permutations. These numbers can get very large, so output the remainder of division by 1000000007 instead.

The first line of input contains two integers `K` and `N` (`2\ ≤\ K\ ≤\ 300000,\ 1\ ≤\ N\ ≤\ 100000`), the length of the base permutation and the number of students.

The next line contains the base permutation – a sequence of `K` integers between `1` and `K` such that each number occurs in a sequence exactly once.

The next `N` lines contain two integers each `A` and `B` (`1\ ≤\ A\ <\ B\ ≤\ K`), indices of two elements that should be swapped to obtain each permutation.

Output `N` integers, one per line, the rank of each permutation modulo 1000000007 in the order they are presented in the input.

5 3
1 5 4 2 3
1 3
2 3
2 5

91
17
9

15 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 15
1 15

2
246045325