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

\((1 \le |N| \le 200\ 000)\)
\((1 \le |H| \le 200\ 000)\)
\(|N| \le 8\)
\(|H| \le 200\)
\(|N| \le 200\)
\(|N| \le 2000\)
\(|H| \le 2000\)

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 2000\) and \(|H| \le 2000\).

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

생성자가 기록되지 않았습니다.

출처 CCC 2020 Senior