Saw Constructor
Time limit2sMemory limit256 MB
Count permutations of n distinct sizes where every even position holds a local maximum, modulo 1e9+7.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Combinatorics, Math, Implementation
- Solved
- No attempts yet
Problem
Ivan is a saw constructor. The goal of a saw constructor is to form a saw profile, that is, an array of tooth sizes. A saw with teeth of different sizes cuts much better than a saw with teeth of the same size.
One day Ivan came across an interesting article. In it, British scientists proved that an ideal saw satisfies the following conditions:
- all teeth of the saw have different sizes,
- the second tooth is larger than the first and the third,
- the fourth tooth is larger than the third and the fifth,
- ...
That is, the tooth sizes must actually form a permutation, and the teeth at even positions must be larger than their neighbors.
Ivan became very interested in the article and wanted to know how many different saws he can make if he has a set of (n) different teeth. Saws obtained from one another by reversing the order of the teeth are considered different. The answer can be quite large, so Ivan decided to find it modulo (10^9 + 7).
For example, from four teeth Ivan can make 5 different saws: ((1, 3, 2, 4)), ((1, 4, 2, 3)), ((2, 3, 1, 4)), ((2, 4, 1, 3)), and ((3, 4, 1, 2)).
Input
The first and only line contains an integer (n), the number of teeth in the saw Ivan wants to make ((1 \le n \le 5,000)).
Output
Output the number of saws modulo (10^9 + 7).