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 | ≤ 2 * 105 ) , the needle string.
The second line contains H ( 1 ≤ | H | ≤ 2 * 105 ) , the haystack string.
Output consists of one integer, the number of distinct permutations of N which appear as a substring of H .
Remember to print a ‘\n’ at the end of the output.