Iterace jazyka

Konečnou množinu znaků nazýváme abecedou. Řetězec, jehož všechny znaky jsou prvky dané abecedy, nazýváme řetězcem nad danou abecedou nebo také slovem nad danou abecedou. Každou množinu řetězců, jejíž všechny řetězce jsou řetězci nad danou abecedou, nazveme jazykem nad danou abecedou.

V této úloze budeme uvažovat pouze abecedu A = {'a', 'b', ..., 'z'} a místo obratů "slovo nad abecedou A", "jazyk nad abecedou A" budeme užívat jednodušší vyjadřování: "Slovo", "jazyk".

Nechť zápis slova s délky m obsahuje po řadě znaky s₁s₂ ...s_m a nechť zápis slova t délky n obsahuje po řadě znaky t₁t₂ ...t_n. Zřetězení slov s a t je slovo u délky m+n obsahující po řadě znaky s₁s₂ ...s_mt₁t₂ ...t_n. Zřetězení slov s a t značíme symbolem s.t.
Zřetězení dvou jazyků L₁ a L₂ je množina všech slov s.t, kde s je slovo jazyka L₁ a t je slovo jazyka L₂. Zřetězení jazyků L₁ a L₂ značíme symbolem L₁.L₂.

Sjednocení dvou jazyků L₁ a L₂ je množina všech slov, která leží v alespoň jednom z jazyků L₁ a L₂, a značíme ji standardně L₁ ∪ L₂.

Mohutnost jazyka je rovna počtu slov, které jazyk obsahuje.

Pro libovolný jazyk L a pro kladné celé číslo k definujeme další jazyk, který budeme nazývat k-tá iterace jazyka L a který budeme značit L^k, takto:
1. Pro k = 1 je L^k = L.
2. Pro k > 1 je L^k = L^k−1.L.

Úloha
Na vstupu je dán jazyk L, a kladné číslo K, máme určit mohutnost sjednocení L¹ ∪ L² ∪ ... ∪ L^K.

Vstup

První řádek vstupu obsahuje dvě celá kladná čísla M, K navzájem oddělená mezerou. Číslo M představuje mohutnost zadaného jazyka L. Každý z dalších M řádků obsahuje jeden řetězec nad abecedou {'a', 'b', ..., 'z'}, který představuje slovo jazyka L. Všechna slova na vstupu jsou navzájem různá, mohutnost L nepřesáhne 20, délka jednotlivých slov nepřesáhne 50.

Výstup

Výstup obsahuje jediný textový řádek s jedním celým číslem představujícím mohutnost jazyka L¹ ∪ L² ∪ ... ∪ L^K. Tato hodnota nepřesáhne 2×10⁶.

Příklad 1

Vstup:

2 2
abc
def

Výstup:

6

Příklad 2

Vstup:

4 3
a
ab
aaaa
b

Výstup:

66

Příklad 3

Vstup:

10 6
a
b
c
d
e
f
g
h
i
j

Výstup:

1111110

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