레이팅 미적용설명
텍스트 \(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\)로 나눈 나머지를 출력한다.
예제 1
입력
aaa
a
출력
3
예제 2
입력
aaa
aa
출력
3
예제 3
입력
abab
ab
출력
3
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그