## CCC '20 S3 - Searching for Strings

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Note: This problem originated from the 2020 CCC Senior contest. CBOJ is in no way affiliated with the CEMC.

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).

#### Input Specification

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

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

#### Output Specification

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

#### Sample Input

aab
abacabaa

#### Output for Sample Input

2

#### Explanation of Output for Sample Input

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