Tienes una cadena N, llamada aguja, y una cadena H, llamada pajar, las cuales contienen solo letras minúsculas \(a..z\).

Escribe un programa para contar el número de permutaciones distintas de N que aparecen como una subcadena de H al menos una vez. Ten en cuenta que N puede tener entre 1 y \(N.length!\) permutaciones distintas en total; por ejemplo, la cadena aab tiene 3 permutaciones distintas (aab, aba y baa).

Entrada

La primera línea contiene la aguja, una string entre 1 y 200000 carácteres

La primera línea contiene el pajar, una string entre 1 y 200000 carácteres

Salida

El número de distintas permutaciones de N que hay en H

Ejemplo de Entrada 1

aab
abacabaa

Ejemplo de Salida 1

2