UDP 문자열

시간 제한1초메모리 제한1024 MB

요약

U, D, P가 각각 N개씩 들어 있는 길이 3N인 문자열 중, 두 UDP 문자열을 이어 붙여 만들 수 없는 완전 UDP 문자열의 개수를 10^9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

U, D, P로만 이루어져 있으며 U, D, P가 모두 동일한 개수가 들어 있는 문자열을 UDP 문자열이라고 한다. 또한, 어떤 두 개의 UDP 문자열을 이어 붙여도 만들 수 없는 UDP 문자열을 완전 UDP 문자열이라고 한다. 가령, 문자열 UDPPUD는 두 UDP 문자열 UDP와 PUD를 이어붙여 만들 수 있으므로 완전 UDP 문자열이 아니지만, UUDDPP는 완전 UDP 문자열이다.

길이 $3N$ 인 완전 UDP 문자열의 개수를 구해보자. 단, 답이 매우 클 수 있으므로 답을 $10^9+7$ 로 나눈 나머지를 구해보자.

입력

첫 번째 줄에 UDP 문자열의 길이를 $3$ 으로 나눈 정수 $N$ 이 주어진다. $(1\leq N\leq 5\\,000)$

출력

길이 $3N$ 인 완전 UDP 문자열의 개수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제2

예제 1
입력
```
1
```
예상 출력
```
6
```
예제 2
입력
```
2
```
예상 출력
```
54
```