Uolevilla on n sanaa, joista hän haluaa tehdä sanaketjun. Sanaketjussa seuraavan sanan täytyy alkaa samalla kirjaimella kuin mihin edellinen sana päättyy. Uolevi haluaa käyttää kaikki sanat sanaketjuun.

Esimerkiksi CEMBALO–OMENA–APINA on kelvollinen sanaketju.

Tehtäväsi on laskea, kuinka monta erilaista sanaketjua Uolevi voi muodostaa.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: sanojen määrä.

Tämän jälkeen syötteessä on n riviä, joista jokaisella on yksi sana. Sana muodostuu kirjaimista A..Z ja siinä on enintään 100 merkkiä.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako erilaista sanaketjua Uolevi voi tehdä sanoista.

Rajat

• 1 \le n \le 16

Esimerkki

Syöte:

3
APINA
CEMBALO
OMENA

Tuloste:

1