MR.DR 문자열
시간 제한1초메모리 제한1024 MB
길이가 N인 대문자 문자열 중에서 부분 수열로 MRDR을 포함하는 문자열의 개수를 10^9+7로 나눈 나머지를 구한다.
문제
국민대학교의 정문에 앉아있는 Mr.Doctor
길이가 이상인 영어 대문자로만 이루어질 수 있는 서로 다른 모든 문자열에 대해, 개 이상의 문자를 제거하였을 때 문자열 MRDR이 되는 문자열을 MR.DR 문자열이라고 한다.
정수 이 주어질 때, 길이가 인 MR.DR 문자열의 개수를 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 정수 이 주어진다. ()
출력
길이가 인 MR.DR 문자열의 개수를 출력하라.
이때 정답이 매우 커질 수 있으므로 정답을 로 나눈 나머지를 출력하라.