## CCC '20 S3 Easy - Searching for Strings

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

## Comments