두 개의 DNA 가닥 \(A\), \(B\) 가 주어진다. 연구원은 두 가닥에서 동시에 나타나는 서로 다른 공통 부분 수열의 개수를 세고 싶다.

문자열 \(T\) 가 \(A\) 의 부분 수열이면서 동시에 \(B\) 의 부분 수열일 때, \(T\) 를 \(A\) 와 \(B\) 의 공통 부분 수열이라고 한다. 빈 문자열도 공통 부분 수열에 포함한다. 내용이 같은 부분 수열은 (등장 위치가 달라도) 하나로 센다.

즉 서로 다른 문자열의 개수를 세는 것이다. 그 개수가 매우 커질 수 있으므로 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력하여라.

예를 들어 \(A=\) ab, \(B=\) ab 라면 공통 부분 수열은 (빈 문자열), a, b, ab 의 4개이다.

\(1 \le |A|, |B| \le 2{,}000\), 두 문자열은 소문자 알파벳으로만 이루어진다.

첫째 줄에 문자열 \(A\), 둘째 줄에 문자열 \(B\) 가 주어진다. 두 문자열 모두 소문자 알파벳으로만 이루어진다. (\(1 \le |A|, |B| \le 2{,}000\))

서로 다른 공통 부분 수열의 개수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력한다. (빈 문자열 포함)

riseoj 작성

출처 Original