문자열 찾기

문자열 $N$과 문자열 $H$가 주어진다. $N$은 바늘이라 하고 $H$는 건초더미라 한다. 두 문자열은 모두 알파벳 소문자 “a”부터 “z”까지로만 이루어져 있다.

$N$의 서로 다른 순열 중 $H$의 부분 문자열로 한 번 이상 등장하는 것의 개수를 세는 프로그램을 작성하시오. $N$의 서로 다른 순열은 총 $1$개부터 $|N|!$개까지 있을 수 있다. 예를 들어 문자열 “aab”의 서로 다른 순열은 “aab”, “aba”, “baa” 세 개이다.

첫째 줄에 바늘 문자열 $N$이 주어진다. ($1 \le |N| \le 200\,000$)

둘째 줄에 건초더미 문자열 $H$가 주어진다. ($1 \le |H| \le 200\,000$)

$N$의 서로 다른 순열 중 $H$의 부분 문자열로 등장하는 것의 개수를 한 정수로 출력한다.