Ketju

• Time limit: 1.00 s
• Memory limit: 128 MB

Annettuna on $n$ merkkijonoa, jotka kuvaavat DNA-ketjun osia. Tehtäväsi on liittää ne kaikki ketjuksi. Rajoituksena on, että kun osat liitetään peräkkäin, niin edellisen osan viimeisen merkin tulee olla sama kuin seuraavan osan ensimmäinen merkki.

Monellako tavalla voit muodostaa ketjun? Kaksi tapaa ovat erilaiset, jos valitset jossakin vaiheessa eri kohdassa olevan merkkijonon seuraavaksi.

Syöte

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

Sitten syötteessä on $n$ riviä, joista jokainen kuvaa yhden osan. Osa muodostuu merkeistä A, C, G ja T, ja siinä on korkeintaan 10 merkkiä.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: monellako tavalla ketjun voi muodostaa.

Rajat

• $1 \le n \le 20$
  

Esimerkki

Syöte:
5
ACGA
ACGA
ACAC
CCCC
CTAC

Tuloste:
4