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.