Asistent

Profesor Danko predaje matematiku na jednom sveučilištu gdje njegov predmet ovaj semestar pohađa N studenata. Na zadnjem predavanju, Danko je studentima pričao o permutacijama i njihovom prebrojavanju. Niz od K cijelih brojeva od 1 do K gdje se svaki broj u nizu pojavljuje točno jednom, moguće je permutirati (tj. preurediti poredak) na ukupno K! načina. Na primjer, niz (1, 2, 3) može se permutirati na 3! = 6 načina. Permutacije jednog niza meñusobno su poredane tako da se prvo usporeñuje prvi broj u permutaciji, zatim drugi, treći i tako dalje:
1. (1, 2, 3)
2. (1, 3, 2)
3. (2, 1, 3)
4. (2, 3, 1)
5. (3, 1, 2)
6. (3, 2, 1)
Redni broj permutacije u poretku svih permutacija niza nazivamo rang permutacije. Na primjer, rang permutacije (3, 1, 2) je 5. Danko je svakom od svojih studenata zadao jednu permutaciju za domaću zadaću za koju student mora odrediti rang. Kako ne bi morao smišljati N različitih permutacija, a opet da bi svaki student imao različit zadatak, Danko je permutacije generirao na sljedeći način: Smislio je jednu permutaciju niza od K brojeva, nazovimo ju “osnovna permutacija”, a svaku od N permutacija za studente dobio je jednom zamjenom neka dva elementa osnovne permutacije.
Dankov asistent Janko mora ispraviti sve te domaće zadaće. Profesor mu je dao osnovnu permutaciju i N parova brojeva, pozicije dvaju elemenata koji su zamijenjeni u zadaći pojedinog studenta. Na primjer, ako je osnovna permutacija (1, 5, 4, 2, 3), a parovi pozicija su (1, 3), (2, 3) i (2, 5), tada su tri
permutacije koje su studenti dobili za zadaću (4, 5, 1, 2, 3), (1, 4, 5, 2, 3) i (1, 3, 4, 2, 5), a njihovi rangovi su 91, 17 i 9. Napišite program koji će pomoći Janku i odrediti rangove permutacija koje su studenti dobili za zadaću.
Kako ti brojevi mogu biti vrlo veliki, ispišite samo ostatak pri dijeljenju tih brojeva sa 1 000 000 007.