단어를 포함하는 순열

영어 소문자로 이루어진 단어 $A$와 $B$가 주어진다. $A$의 글자를 모두 사용해 다시 배열하면 여러 단어를 만들 수 있다. 이렇게 만들 수 있는 서로 다른 단어 중에서 $B$를 연속한 부분 문자열로 포함하는 단어가 몇 개인지 세어라. 배열 방법이 달라도 결과가 같은 단어라면 한 번만 센다.

개수를 $10007$로 나눈 나머지를 구한다.

첫째 줄에 영어 소문자로 이루어진 단어 $A$가 주어진다. $A$의 길이는 $500$보다 크지 않다.

둘째 줄에 영어 소문자로 이루어진 단어 $B$가 주어진다. $B$의 길이는 $A$의 길이보다 길지 않다.

첫째 줄에 조건을 만족하는 단어의 개수를 $10007$로 나눈 나머지를 출력한다.

$A$가 mirko이고 $B$가 mir이면 조건을 만족하는 단어는 kmiro, komir, mirko, mirok, okmir, omirk 여섯 개다.