Solution Relay

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to call students in N rows of two so everyone hears the solution and no two consecutive rows lack a relay, modulo 10^9+7.

Level: Medium4 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

Hyeon teaches an algorithm class. There are $2N$ students, seated in $N$ rows of two, one pair per row, front to back. Hyeon calls some students up to explain the solution to today's problem. After the explanation, the students return to their seats. If a student's partner did not hear the explanation, the student passes it on to the partner. Every student must hear the solution from Hyeon or from their partner, and in at least one of any two consecutive rows, a relay to the partner must happen. Count the ways Hyeon can call students so that this condition holds. The answer can be large, so print it modulo $10^9 + 7$ .

Input

The first line contains a natural number $N$ .

Output

Print the number of ways Hyeon can call students, modulo $10^9 + 7$ .

Constraints

$N$ is an integer.

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

Examples2

Example 1
Input
```
1
```
Expected output
```
3
```
Example 2
Input
```
2
```
Expected output
```
8
```