8695번 - Pociąg 다국어

Mały Jacuś dostał od mamy pociąg złożony z n wagonów. Po dokładnym obejrzeniu każdego z nich stwierdził, że na odwrocie wagonów znajduje się numer seryjny złożony z małych liter alfabetu angielskiego.

Mały Jacuś może układać wagony w dowolnej kolejności, budując w ten sposób pociąg (zawsze z n wagonów), który po odwróceniu tworzy pewien tekst w. Znudziło mu się to dość szybko, ponieważ chciał zająć się informatyką. W związku z tym wymyślił zadanie.

Poprosił mamusię, aby napisała na kartce pewien tekst t. Tekst w uznał za wzorzec, którego będzie szukał w tekście t. Jacuś chce policzyć sumę wystąpień wszystkich wzorców (zbudowanych z każdej permutacji pociągu) w tekście t.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 ≤ n < 10). W n kolejnych wierszach znajduje się tekst w_i oznaczający numer seryjny i - tego wagonu (długość numeru seryjnego nie przekracza 10⁵). W kolejnym wierszu znajduje się tekst t (długość tekstu t nie przekracza 10⁶).

W jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita, równa sumie wystąpień wszystkich wzorców.