단어 퍼즐

Anna는 최근 휴대폰 단어 퍼즐 앱에 빠져 있다. 단어 퍼즐은 몇 개의 빈칸이 있는 하나의 영어 단어다. 각 빈칸은 채워야 할 글자 하나를 나타낸다. 예를 들어 단어 “programming”은 퍼즐 p_o_rammin_으로 나타날 수 있다. Anna는 퍼즐을 풀 때 먼저 빈칸 하나를 클릭하고 글자를 입력하기 시작한다. Anna가 글자를 입력하면 앱이 자동으로 다음 빈칸으로 넘어간다. 채운 글자 오른쪽에 빈칸이 더 이상 없으면 앱은 단어의 처음으로 되돌아가서 거기서부터 다시 진행한다. Anna는 모든 빈칸을 채울 때까지 글자를 계속 입력한다. 퍼즐 p_o_rammin_을 풀기 위해 Anna는 첫 번째 빈칸을 클릭하고 rgg를 입력할 수 있다. 또는 두 번째 빈칸을 클릭하고 ggr을 입력할 수도 있다.

어느 날 Anna는 자신이 푼 퍼즐과 자신이 입력한 글자 순서를 보여 준다. Anna가 푼 퍼즐이 될 수 있는 서로 다른 퍼즐은 몇 개일까? 두 퍼즐은 빈칸의 위치가 다르면 서로 다르다. 예를 들어 퍼즐 단어가 programming이고 Anna가 rgg를 입력했다면 가능한 퍼즐은 p_o_rammin_과 pro__ammin_ 두 가지다. 답이 클 수 있으므로 답을 1,000,000,007로 나눈 나머지를 출력한다.

첫째 줄에 퍼즐 단어를 나타내는 문자열 p가 주어진다. (1 ≤ |p| ≤ 105) 둘째 줄에 Anna가 입력한 글자 순서를 나타내는 문자열 s가 주어진다. (1 ≤ |s| ≤ min(50, |p|)) 두 문자열은 모두 알파벳 소문자로만 이루어져 있다.

Anna가 푼 퍼즐이 될 수 있는 서로 다른 퍼즐의 개수를 1,000,000,007로 나눈 나머지로 출력한다. Anna가 s를 입력해서 퍼즐을 풀 수 없다면 0을 출력한다.