Code Submission Evaluation System Login

Datatähti-valmennus

Ketju


Task | Statistics


CSES - 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
Esimerkki

Syöte:
5
ACGA
ACGA
ACAC
CCCC
CTAC


Tuloste:
4