Noitapelissä on n pelaajaa, joista 3 on noitia ja n-3 on kyläläisiä. Kyläläisten tehtävänä on selvittää, ketkä pelaajat ovat noitia.

Alussa jokainen pelaaja saa tietää oman roolinsa. Lisäksi jokainen noita saa tietää, ketkä muut ovat noitia, mutta kyläläiset eivät saa tietoa rooleista. Kyläläisten tehtävänä on onnistua selvittämään noidat pelin aikana.

Pelissä järjestetään äänestys, jossa jokainen pelaaja syyttää yhtä toista pelaajaa noidaksi. Noita ei koskaan syytä pelaajaa, joka todellisuudessa on noita. Sen sijaan kyläläinen voi syyttää joko toista kyläläistä tai noitaa.

Sinulle annetaan äänestyksen tulokset ja tehtäväsi on selvittää, montako mahdollista tapaa on, ketkä pelaajat ovat noitia.

Syöte

Ensimmäisellä rivillä on kokonaisluku n: pelaajien määrä. Pelaajat on numeroitu 1,2,\ldots,n.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n. Tässä x_k on sen pelaajan numero, jota pelaaja k syyttää noidaksi.

Tuloste

Tulosta yksi kokonaisluku: montako mahdollista tapaa on, ketkä pelaajat ovat noitia.

Esimerkki

Syöte:

6
2 5 4 1 4 5

Tuloste:

4

Selitys: Noidat voivat olla (1,3,5), (1,3,6), (2,3,6) tai (2,4,6).

Osatehtävä 1 (23 pistettä)

• 3 \le n \le 100

Osatehtävä 2 (24 pistettä)

• 3 \le n \le 5000

Osatehtävä 3 (53 pistettä)

• 3 \le n \le 10^5