31828번 - MR.DR 문자열

문제

국민대학교의 정문에 앉아있는 Mr.Doctor

길이가 4ドル$ 이상인 영어 대문자로만 이루어질 수 있는 서로 다른 모든 문자열에 대해, 0ドル$개 이상의 문자를 제거하였을 때 문자열 MRDR이 되는 문자열을 MR.DR 문자열이라고 한다.

정수 $N$이 주어질 때, 길이가 $N$인 MR.DR 문자열의 개수를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 정수 $N$이 주어진다. (4ドル \leq N \leq 100\ 000$)

출력

길이가 $N$인 MR.DR 문자열의 개수를 출력하라.

이때 정답이 매우 커질 수 있으므로 정답을 1ドル\ 000\ 000\ 007 (=10^{9} + 7)$로 나눈 나머지를 출력하라.

제한

힌트