문제 설명
연속하는 총 \(N\)개의 칸이 다음과 같이 있다.
각 위치에 블록을 쌓는 놀이를 하려고 한다. 이때, 다음과 같은 규칙이 있다.
단, 수가 커질 수 있으므로 \(10^9+7\)로 나눈 나머지를 출력하시오.
각 위치에 블록을 쌓는 놀이를 하려고 한다. 이때, 다음과 같은 규칙이 있다.
- 첫 칸과 마지막 칸은 블록이 없어야 한다.
- 인접한 칸과의 블록 개수 차이는 \(1\) 이하여야 한다.
단, 수가 커질 수 있으므로 \(10^9+7\)로 나눈 나머지를 출력하시오.
입력 설명
칸의 개수 \(N\)이 자연수로 주어진다.
\((1 \le N \le 5000)\)
\((1 \le N \le 5000)\)
출력 설명
쌓을 수 있는 경우의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.
입력 예시 Copy
3
출력 예시 Copy
2
도움
다이나믹 프로그래밍