Canadian Computing Competition: 2020 Stage 1, Senior #3

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.

For ~3~ of the ~15~ available marks, ~|N| \le 8~ and ~|H| \le 200~.

For an additional ~2~ of the ~15~ available marks, ~|N| \le 200~ and ~|H| \le 200~.

For an additional ~2~ of the ~15~ available marks, ~|N| \le 2\,000~ and ~|H| \le 2\,000~.

Because the original test data were weak, an additional subtask worth ~5~ marks has been added.

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.