Ion este un lingvist pasionat. Recent el a descoperit un text scris intr-o limba necunoscuta. Textul este scris pe mai multe linii si este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spatii sau/si semne de punctuatie $(,:;.!?-)$.
Ion a fost frapat ca exista multe similitudini intre cuvintele din text. Fiind foarte riguros, Ion defineste similitudinea a doua cuvinte dupa cum urmeaza.

Fie $c$<sub>1</sub> si $c$<sub>2</sub> doua cuvinte. Cuvantul $c$<sub>1</sub> poate fi obtinut din cuvantul $c$<sub>2</sub> printr-o succesiune de operatii elementare. Operatiile elementare ce pot fi folosite sunt:

Fie $c$~1~ si $c$~2~ doua cuvinte. Cuvantul $c$~1~ poate fi obtinut din cuvantul $c$~2~ printr-o succesiune de operatii elementare. Operatiile elementare ce pot fi folosite sunt:

| Operatia
| Efect
| Exemplu

|_. Operatia
|_. Efect
|_. Exemplu

|

| $move$({$c$}<sub>1</sub>,{$c$}<sub>2</sub>)
| Muta primul caracter din $c$<sub>1</sub> la sfarsitul cuvantului $c$<sub>2</sub>
| Daca $c$<sub>1</sub>$="alba"$ si $c$<sub>2</sub>$="neagra"$, dupa efectuarea operatiei $move$({$c$}<sub>1</sub>,{$c$}<sub>2</sub>), $c$<sub>1</sub> va fi $"lba"$, iar $c$<sub>2</sub> va fi $"neagraa"$.

| {$move(c$}~1~{$,c$}~2~{$)$}
| Muta primul caracter din $c$~1~ la sfarsitul cuvantului $c$~2~
| Daca $c$~1~{$="alba"$} si $c$~2~{$="neagra"$}, dupa efectuarea operatiei{$move(c$}~1~{$,c$}~2~{$)$}, $c$~1~ va fi $"lba"$, iar $c$~2~ va fi $"neagraa"$.

|

| $insert$({$c$}<sub>1</sub>,{$x$})
| Insereaza caracterul $x$ la inceputul lui $c$<sub>1</sub>
| Daca $c$<sub>1</sub>$="alba"$ si $x='b'$, dupa executarea operatiei $insert$({$c$}<sub>1</sub>,{$x$}), $c$<sub>1</sub> va fi $"balba"$.

| {$insert(c$}~1~{$,x)$}
| Insereaza caracterul $x$ la inceputul lui $c$~1~
| Daca $c$~1~{$="alba"$} si $x='b'$, dupa executarea operatiei {$insert(c$}~1~{$,x)$}, $c$~1~ va fi $"balba"$.

|

| $delete$({$c$}<sub>1</sub>)
| Sterge primul caracter din $c$<sub>1</sub>
| Daca $c$<sub>1</sub>$="alba"$, dupa executarea operatiei $delete$({$c$}<sub>1</sub>), $c$<sub>1</sub> va fi $"lba"$.

| {$delete(c$}~1~$)$
| Sterge primul caracter din $c$~1~
| Daca $c$~1~{$="alba"$}, dupa executarea operatiei {$delete(c$}~1~$)$, $c$~1~ va fi $"lba"$.

|

Definim similitudinea dintre $c$<sub>1</sub> si $c$<sub>2</sub> ca fiind numarul minim de operatii $insert$ si $delete$ ce trebuie sa fie executate pentru a transforma cuvantul $c$<sub>1</sub> in cuvantul $c$<sub>2</sub> (operatiile $move$ nu se numara).
Fie $c$<sub>o</sub> primul cuvant din text. Incepand cu $c$<sub>o</sub> putem construi lanturi de $k-similitudine$.

Definim similitudinea dintre $c$~1~ si $c$~2~ ca fiind numarul minim de operatii $insert$ si $delete$ ce trebuie sa fie executate pentru a transforma cuvantul $c$~1~ in cuvantul $c$~2~ (operatiile $move$ nu se numara).
Fie $c$~0~ primul cuvant din text. Incepand cu $c$~0~ putem construi lanturi de $k-similitudine$.

Un lant de $k-similitudine$ este o succesiune de cuvinte distincte din text cu urmatoarele proprietati:
* daca cuvantul $x$ apare in lant inaintea cuvantului $y$, atunci prima aparitie a lui $x$ in text preceda prima aparitie a lui $y$ in text;

h2. Cerinta

Scrieti un program care sa determine numarul de lanturi de $k-similitudine$ care incep cu $c$<sub>o</sub>.

Scrieti un program care sa determine numarul de lanturi de $k-similitudine$ care incep cu $c$~0~.

h2. Date de intrare

h2. Date de iesire

Fisierul de iesire $lant.out$ va contine o singura linie pe care va fi scris numarul de lanturi de $k-similitudine$ care incep cu $c$<sub>o</sub>.

Fisierul de iesire $lant.out$ va contine o singura linie pe care va fi scris numarul de lanturi de $k-similitudine$ care incep cu $c$~0~.

h2. Restrictii
* Lungimea unei linii din text nu depaseste $1000$ de caractere.
* Lungimea unui cuvant nu depaseste $30$ de caractere.

* Numarul total de cuvinte distincte $≤150$.
* Pentru datele de test, numarul de lanturi de $k-similitudine$ care incep cu $c$<sub>o</sub> va fi $&le;2000000000$ (doua miliarde).

* Numarul total de cuvinte distincte $≤ 150$.
* Pentru datele de test, numarul de lanturi de $k-similitudine$ care incep cu $c$~0~ va fi $≤2000000000$ (doua miliarde).

h2. Exemplu

== include(page="template/taskfooter" task_id="lant") ==

==SmfTopic(topic_id="2063")==

2063