Searching for Strings

문제

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”).

입력

The first line contains N (1 ≤ |N| ≤ 200 000), the needle string.

The second line contains H (1 ≤ |H| ≤ 200 000), the haystack string.

출력

Output consists of one integer, the number of distinct permutations of N which appear as a substring of H.