## CCC '20 S3 - Searching for Strings

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

## Comments