15194번 - Cod

U deathmatch varijanti popularne računalne igre, n igrača se medusobno bori u virtualnom svijetu., Bodovi igrača x se sastoji od dva cijela broja f_x i d_x — redom ukupan broj puta igrač x je ubio nekog drugog igrača i ukupan broj puta igrač x je ubijen od strane nekog drugog igrača. Dakle, kada tijekom igre igrač x ubije igrača y onda se f_x i d_y povećaju za jedan (a igrač y se, naravno, ponovno pojavljuje i nastavlja s igrom). Nije moguće da neki igrač ubije samog sebe, niti je moguće da se dva ubijanja dogode istovremeno. Igra završava čim neki igrač ostvari točno n ubijanja.

Rezultat završene igre je tablica koja se sastoji od n redaka i 2 stupca, gdje svaki redak sadrži bodove jednog igrača i to redom f_x i d_x. Igrači su u tablici poredani silazno po bodovima — najprije dolaze oni sa većom vrijednošću f_x, a medu onima sa jednakom vrijednošću, f_x najprije dolaze oni sa manjom vrijednošću d_x.

Djelomični rezultat je rezultat završene igre iz kojeg su izbrisane neke vrijednosti u tablici. Zadan je jedan djelomični rezultat, neka je m ukupan broj ispravnih rezultata od kojih je mogao nastati zadani djelomični rezultat. Odredite koliko je m modulo 10⁹ + 7.

U prvom redu se nalazi prirodni broj n (2 ≤ n ≤ 10) — broj igrača. U k-om od sljedećih n redova se nalaze se dva cijela broja f_k i d_k (−1 ≤ f_k ≤ n, −1 ≤ d_k ≤ n²) — k-ti redak djelomičnog rezultata. Izbrisane vrijednosti su označene brojem −1.

Zadani djelomični rezultat je ispravan u smislu da je dobiven od nekog rezultata završene igre na opisani način.

Ispišite traženi broj mogućih originalnih rezultata modulo 10⁹ + 7.

U prvom primjeru test podataka, mogući originalni rezultati su (2 0, 0 2) i (2 1, 1 2).