Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: stalai.in

Rezultatų failas: stalai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Stalai

Į kompaniją buvo atvežti nauji stalai. Jums paskirta užduotis sukurti darbuotojų sėdėjimo vietų schemą. Stalai yra sunumeruoti. Jūs išsiuntėte kiekvienam darbuotojui užklausą, prie kurio stalo šiuo metu darbuotojas dirba bei prie kurio stalo norėtų dirbti (gali būti, jog darbuotojas norės dirbti prie to pačio stalo, prie kurio dirba šiuo metu). Kiekvienas darbuotojas turi likti dabartinėje vietoje arba persikelti į naują norimą vietą. Šiuo metu jokie du darbuotojai nedirba prie to pačio stalo bei įvykdžius perkėlimus taip pat negali dirbti keliese prie vieno stalo.

Jūsų užduotis - suskaičiuoti, kiek skirtingų darbuotojų išdėstymų galima padaryti laikantis apibūdintų reikalavimų.

Pradiniai duomenys

Pirmoje eilutėje duotas vienas skaičius n (1\\leqn\\leq10^5) - darbuotojų skaičius.

Sekančiose n eilučių duota po 2 skaičius - dabartinė i-tojo darbuotojo vieta, bei norima darbuotojo vieta.

Rezultatai

Išveskite vieną skaičių - kiek skirtingų darbuotojų išdėstymų galima padaryti laikantis apibūdintų reikalavimų moduliu 1000000007.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
1 5
5 2
3 7
7 3
 
6