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.