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)$로 나눈 나머지를 출력하라.