Podřetězce

Je dána množina R několika řetězců stejné kladné délky K. Každý z řetězců množiny R je sestaven pouze ze znaků 'A', 'B', 'C', 'D' a každý tento znak se může v řetězci vyskytovat vícekrát nebo v něm může docela chybět.

Je dáno celé kladné číslo L. Dále je dána množina S všech navzájem různých řetězců délky L, která má navíc tu vlastnost, že každý podřetězec délky K každého jejího prvku je zároveň prvkem množiny R. Za podřetězec považujeme vždy souvislou podposloupnost znaků daného řetězce.

Úloha
Máme určit mohutnost množiny S.

Vstup

Na vstupu je více řádků. První řádek obsahuje číslo L. Na dalších řádcích je uvedena množina R, tak, že každý její prvek je zapsán na právě jednom řádku. Poslední řádek vstupu obsahuje jediný znak '*' (hvězdička), tento znak ukončuje výčet prvků množiny R a nepatří do ní. Vstup neobsahuje mezery ani prázdné řádky.
Hodnota L nepřekročí 200, mohutnost R nepřekročí 50 a hodnota K nepřekročí 15.

Výstup

Na výstupu je jeden textový řádek s jedním celým číslem představujícím mohutnost množiny S. Mohutnost množiny S nepřekročí hodnotu 2⁶³−1.

Příklad 1

Vstup:

10
AB
BB
BA
*

Výstup:

144

Všimněte si, že 144 je třináctým prvkem Fibonacciho posloupnosti {0, 1, 1, 2, 3, 5, 8, 13, 21, ... }.

Příklad 2

Vstup:

106
ABB
BBC
BBA
BAA
AAB
BCA
CAB
CBB
BCB
*

Výstup:

309478917640396

Příklad 3

Vstup:

15
ABB
BBB
BBA
BAB
*

Výstup:

406

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data