Proglute

Time limit2sMemory limit1024 MB

Summary

Count the non-crossing string sets on N circular pegs where every peg has two strings except two endpoint pegs with one, modulo 10^9+7.

Level: Medium6 of 10
Topics: Dynamic programming, Graph, Combinatorics
Solved: No attempts yet

Problem

Baroque opera enthusiasts at Tomorrow Programming School are developing a new string instrument for their experimental performances. The instrument, called the programmed lute or proglute for short, has a flat circular body with N pegs on its perimeter, labeled with integers from 1 to N.

Each string is stretched between two different pegs and runs across the body without crossing any other string. Every peg except two, called the principal pegs, has two strings attached. Each principal peg has only one string.

The strings are arranged so that a musician can touch the string at one principal peg and slide a finger along the strings to the other principal peg. The finger stays on a string the whole time and moves to another string only at their shared end peg.

The characteristic of a string is the unordered pair of labels of its end pegs. The characteristic of the proglute is the set of all its string characteristics. Two arrangements are different when their characteristics differ.

The figure below shows two possible arrangements for a proglute with five pegs:

Count the number of different string arrangements on the proglute.

Input

The input is a single line with an integer $N$ ( $2 \le N \le 1000$ ), the number of pegs on the perimeter.

Output

Print the number of different string arrangements modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
5
```
Expected output
```
20
```
Example 2
Input
```
666
```
Expected output
```
61847156
```