Sorting
시간 제한1초메모리 제한1024 MB
임의의 두 원소를 교환하는 최소 횟수가 인접한 원소만 교환하는 최소 횟수보다 작은 크기 N 순열의 개수를 999017로 나눈 나머지를 구한다.
문제
Instead of partying in the Bellagio, Johnnie spends his time sorting permutations. He chooses a random permutation having N elements. While this permutation is not sorted, Johnnie picks two consecutive elements and swaps them. After a while he learns how to sort any permutation using the algorithm above with a minimum number of swaps.
Last night Johnnie learnt a new algorithm, so now he can swap any two elements in the permutation. Johnnie will sort the permutation using a minimum number of swaps. Obviously, this new algorithm will use less or the same number of swaps as the old one.
You have to find how many permutations having N elements can be sorted with fewer swaps using the new algorithm. You should print the result modulo 999017.
입력
On the first line of the standard input there is one number N, the length of permutations.
출력
Print the answer modulo 999017 on the first line of the standard output.
제한
- 2 ≤ N ≤ 1000
힌트
There are 11 permutations with the mentioned property:
- 1 4 3 2
- 2 4 3 1
- 3 2 1 4
- 3 2 4 1
- 3 4 1 2
- 3 4 2 1
- 4 1 3 2
- 4 2 1 3
- 4 2 3 1
- 4 3 1 2
- 4 3 2 1
For example, the permutation 4 2 1 3 can be sorted using the first algorithm like this: 4 2 1 3 => 2 4 1 3 => 2 1 4 3 => 1 2 4 3 => 1 2 3 4. Four steps were necessary. Using the second algorithm, it can be sorted faster: 4 2 1 3 => 4 2 3 1 => 1 2 3 4. Only two steps were necessary.