문제
알파벳 소문자로 된 문자열 S와 T가 주어진다.
S의 길이는 N이고 T의 길이는 K이다.
문자열에서 문자 몇 개를 뽑아 순서대로 나열한 것을 부분 서열이라고 한다.
예를 들어, "abc"는 "abbcc"의 부분 서열이다.
당신이 할 일은 S와 T가 주어지면 S의 부분서열 중 T가 몇 개인지 구하는 것이다.
그 개수가 너무 많을 수 있으니 10억7로 나눈 나머지를 출력하면 된다.
입력
첫째 줄에 S가 주어진다.
둘째 줄에 T가 주어진다.
<제한>
1 <= N <= 100000
1 <= K <= 100
S와 T는 알파벳 소문자로 이루어져 있다.
테스트 케이스 중 50%는 T가 "abc"이다.
출력
S의 부분서열중 T의 개수를 10억7로 나눈 나머지를 출력하라.
예제
abbcc
abc
4
출처
20201030 집중강화학습1차3번,songc,IamCoder 38기 선발고사
로그인해야 코드를 작성할 수 있어요.