텍스트 \(T\)와 패턴 \(P\)가 주어질 때, \(T\)에서 인덱스 \(i_1 < i_2 < \dots < i_{|P|}\)를 골라 그 문자들이 \(P\)를 이루도록 하는 경우의 수(즉 \(P\)가 \(T\)의 부분 수열로 나타나는 횟수)를 세시오. 그 값을 \(10^9+7\)로 나눈 나머지를 출력한다. 예를 들어 a는 aaa의 부분 수열로 \(3\)번 나타난다.

첫째 줄에 \(T\) (\(1 \le |T| \le 200\)), 둘째 줄에 \(P\) (\(1 \le |P| \le 20\))가 주어진다. 두 문자열 모두 소문자로만 이루어진다.

부분 수열 등장 횟수를 \(10^9+7\)로 나눈 나머지를 출력한다.

riseoj 작성

출처 RiseOJ Basics