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