Ограничения: время – 2s/4s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
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.
Input
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
Output `N` integers, one per line, the rank of each permutation modulo 1000000007 in the order they
are presented in the input.
Sample Input 1
5 3
1 5 4 2 3
1 3
2 3
2 5
Sample Input 2
15 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 15
1 15
Sample Output 2
2
246045325
Source: Croatian IOI team trials, 2010