시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 18 5 4 40.000%

문제

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.

예제 입력 1

aab
abacabaa

예제 출력 1

2

The permutations “aba” and “baa” each appear as substrings of H (the former appears twice), while the permutation “aab” does not appear.