You're given a string $N$, called the needle, and a string $H$, called the haystack, both of which contain only lowercase letters $a…z$.

Write a program to count the number of distinct permutations of $N$ which appear as a substring of $H$ at least once. Note that $N$ can have anywhere between $1$ and $|N|!$ distinct permutations in total – for example, the string aab has 3 distinct permutations (aab, aba, and baa).

The first line contains $N\ (1≤|N|≤200,000)$, the needle string.

The second line contains $H\ (1≤|H|≤200,000)$, the haystack string.

Output consists of one integer, the number of distinct permutations of $N$ which appear as a substring of $H$.

2

The permutations aba and baa each appear as substrings of $H$ (the former appears twice), while the permutation aab does not appear.