풀이 전달

면접 대비

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

요약

두 명씩 앉은 N개 줄에서 모든 학생이 풀이를 듣고, 연속한 두 줄 중 적어도 한 줄에서 전달이 일어나도록 학생을 부르는 방법의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

현이는 학생들에게 알고리즘 수업을 한다. 학생은 총 $2N$ 명이 있고, 한 줄에 두 명씩 짝을 지어 앞뒤로 총 $N$ 줄로 앉아 있다. 현이는 몇몇 학생을 불러 오늘 수업에 나온 문제의 풀이를 알려준다. 풀이 설명이 끝나면 학생들은 자리로 돌아가고, 자신의 짝꿍이 풀이를 듣지 못했다면 짝꿍에게 풀이를 전달한다. 이때 모든 학생은 현이 또는 짝꿍에게 풀이를 들어야 하며, 연속된 두 줄 중 적어도 한 줄에서는 짝꿍에게 풀이 전달이 일어나야 한다. 이 조건을 만족하도록 현이가 학생을 부를 수 있는 경우의 수를 구한다. 값이 너무 커질 수 있으니 $10^9 + 7$ 로 나눈 나머지를 출력한다.

입력

첫 번째 줄에 자연수 $N$ 이 주어진다.

출력

현이가 학생을 부를 수 있는 경우의 수를 $10^9 + 7$ 로 나눈 나머지를 출력한다.

제한

$N$ 은 정수이다.

$1 \leq N \leq 1\,000\,000$

예제2

예제 1
입력
```
1
```
예상 출력
```
3
```
예제 2
입력
```
2
```
예상 출력
```
8
```