## CCC '20 S3 Easy - Searching for Strings

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

Problem type

Note: This problem is modified from a problem which 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 substring of $$H$$ which are considered as permutations of $$N$$.

#### 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 substrings of $$H$$ which are permutations of $$N$$.

#### Sample Input

aab
abacabaa

#### Output for Sample Input

3

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