Searching for Strings

Σας δίνεται μια συμβολοσειρά ~N~, που ονομάζεται βελόνα, και μια συμβολοσειρά ~H~, που ονομάζεται άχυρα, οι οποίες περιέχουν μόνο πεζά γράμματα "a".."z".

Γράψτε ένα πρόγραμμα για να μετρήσετε τον αριθμό των διαφορετικών μεταθέσεων της ~N~ που εμφανίζονται ως υποσυμβολοσειρές της ~H~ τουλάχιστον μία φορά. Σημειώστε ότι η ~N~ μπορεί να έχει συνολικά μεταξύ ~1~ και ~\left|N\right|!~ διαφορετικές μεταθέσεις- για παράδειγμα, η συμβολοσειρά "aab" έχει ~3~ διαφορετικές μεταθέσεις ("aab", "aba" και "baa").

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει την ~N\;(1 \le \left|N\right| \le 200\;000)~, τη συμβολοσειρά βελόνα.

Η δεύτερη γραμμή θα περιέχει την ~H\;(1 \le \left|H\right| \le 200\;000)~, τη συμβολοσειρά άχυρα.

Για ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~\left|N\right| \le 8~ και ~\left|H\right| \le 200~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~\left|N\right| \le 200~ και ~\left|H\right| \le 200~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~\left|N\right| \le 2000~ και ~\left|H\right| \le 2000~.

Έξοδος

Η έξοδος θα αποτελείται από έναν ακέραιο αριθμό, τον αριθμό των διαφορετικών μεταθέσεων της ~N~, που εμφανίζονται ως υποσυμβολοσεθρές της ~H~.

Παράδειγμα

input

aab
abacabaa

output

2

Επεξήγηση του παραδείγματος:

Οι μεταθέσεις "aba" και "baa" εμφανίζονται ως υποσυμβολοσειρές της ~H~ (η πρώτη εμφανίζεται δύο φορές), ενώ η μετάθεση "aab" δεν εμφανίζεται.