Zadan je usmjereni graf u kojemu iz svakog vrha izlazi točno jedan brid u neki drugi vrh.

Koliki je najmanji broj vrhova koje iz toga grafa treba obrisati tako da u grafu ne ostane nijedan put duljine dva; drugim riječima, tako da ne postoje neka tri (ne nužno sva različita) vrha a, b, c s bridovima a → b i b → c?

Dodatno, na koliko načina možemo obrisati taj najmanji broj vrhova da bismo ispunili navedeni uvjet?

Ulazni podatci

U prvom je retku prirodan broj n (3 ≤ n ≤ 100 000), broj vrhova grafa. Vrhovi su označeni brojevima od 1 do n.

U i-tom od idućih n redaka prirodan je broj j (i /= j) koji predstavlja brid i → j.

Izlazni podatci

U prvi redak ispišite traženi najmanji broj vrhova koji treba obrisati.

U drugi redak ispišite traženi broj načina, točnije njegov ostatak pri dijeljenju s 1 000 000 007.

Bodovanje

Prvi redak ispisa nosi 3/5, a drugi 2/5 vrijednosti testnog primjera.

U testnim primjerima ukupno vrijednima 20 bodova vrijedi n ≤ 20.

U testnim primjerima ukupno vrijednima 25 bodova, svaki vrh j imat će točno jedan ulazni brid i → j.

Probni primjeri

ulaz

4
3
3
4
3

izlaz

1
2

ulaz

5
4
5
4
2
1

izlaz

2
5

ulaz

6
2
1
2
6
4
5

izlaz

2
6

Pojašnjenje prvog probnog primjera:

Možemo obrisati vrh 3. Alternativno, možemo obrisati vrh 4.

Pojašnjenje drugog probnog primjera:

Možemo obrisati sljedeće parove vrhova: (1, 2), (1, 4), (2, 4), (2, 5), (4, 5).

Pojašnjenje trećeg probnog primjera:

Možemo obrisati sljedeće parove vrhova: (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6).