Muguraș

Muguraș a început în sfârșit să studieze informatică, iar Mugurel, tatăl său, este cel mai mândru de alegerea făcută de el.

Neștiind care este cel mai bun limbaj pentru începători, el a ales să învețe Mac, cel mai simplu limbaj de programare din „Imperiul Rațelor de Cauciuc”.

În limbajul Mac avem doar două tipuri de operații posibile:

• $x := s$ (atribuire directă). După această operație, variabila identificată prin $x$ va reține șirul de caractere dat de $s$.
• $x = a + b$ (atribuire din memorie). După această operație, variabila identificată prin $x$ va reține concatenarea șirurilor de caractere (în această ordine) din variabila identificată prin $a$ și cea identificată prin $b$ (variabilele $a$ și $b$ rămân neschimbate, doar variabila $x$ se modifică).

Cerință

Mugurel vrea să îl trimită pe Muguraș la Olimpiada Locală de Informatică pentru Rațe, dar prima dată trebuie să se asigure că știe să codeze și îi dă să rezolve următoare problemă: după efectuarea a $N$ operații în limbajul Mac, de câte ori apare $S$ ca subșir în variabila $V$?

Din păcate încă este la început de drum, așa că Muguraș vă roagă să îl ajutați să ajungă la Olimpiadă.

Date de intrare

Fișierul de intrare va conține pe prima linie un număr întreg $N$, reprezentând numărul de operații. A doua linie conține două șiruri de caractere, $S$ și $V$, separate printr-un spațiu, reprezentând șirul care trebuie căutat și variabila din care trebuie determinat rezultatul. Următoarele $N$ linii conțin câte un șir de caractere, reprezentând o operație în limbajul de programare Mac.

Date de ieșire

Fișierul de ieșire va conține pe prima linie un singur număr întreg $K$, reprezentând rezultatul cerut.

Restricții și precizări

Notăm cu $|X|$ lungimea denumirii unei variabile și cu $|T|$ lungimea unui șir din atribuirea directă.

• $1 \leq N \leq 100 \ 000$
• $1 \leq |V|, |S| \leq 10$
• $1 \leq |X|, |T| \leq 10$
• Toate denumirile variabilelor și șirurile de caractere conțin doar litere mici ale alfabetului englez.
• Un subșir este o secvență consecutivă de caractere dintr-un șir.
• Variabilele folosite la atribuirea din memorie nu conțin niciodată șiruri de caractere vide.
• Se garantează că $1 \leq K \leq 10^{18}$.
• Se garantează că toate operațiile sunt corecte.
• Muguraș nu vă recomandă să învățați Mac, există limbaje de programare mult mai folositoare.
• Pentru teste în valoare de $5$ puncte, $|X| = 1$ și $|S| = 1$.
• Pentru alte teste în valoare de $5$ puncte, $|S| = 1$.
• Pentru alte teste în valoare de $10$ puncte, $N \leq 15$.
• Pentru alte teste în valoare de $20$ puncte, $|X| = 1$.
• Pentru alte teste în valoare de $60$ de puncte, nu există restricții suplimentare

Exemplul 1

muguras.in

5
abc x
p := ab
q := cdef
x = p + q
q := tabc
x = x + q

muguras.out

2

Explicație

După a treia operație, $x$ va reține șirul abcdef. După a cincea operație, $x$ va reține șirul abcdeftabc, în care șirul abc se regăsește de $2$ ori ca subșir.

Exemplul 2

muguras.in

5
haha v
a := haha
b := haha
c := ha
v = a + b
v = v + c

muguras.out

4

Explicație

După a patra operație, $v$ va reține șirul hahahaha. După a cincea operație, $v$ va reține șirul hahahahaha, în care șirul haha se regăsește de $4$ ori ca subșir (literele dintr-un șir pot să apară în mai multe subșiruri).

Exemplul 3

muguras.in

7
a ax
ax := a
ax = ax + ax
ax = ax + ax
ax = ax + ax
ax = ax + ax
ax = ax + ax
ax = ax + ax

muguras.out

64