시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 855 292 214 32.622%

문제

이전에 A국은 여러개의 소국가로 나누어 졌다. 이번에는 다시 하나의 국가로 합치기 위해서 각 소국가의 대표 N명이 원탁에 모였다.

일단 원탁에는 서로의 이름이 써 있어서, 미리 자리를 배정받았다. 일단 회의를 시작하기 전에 악수를 하고 시작하려고 한다. 각각의 대표는 단 한사람과만 악수를 할 수 있다. 모든 악수는 동시에 일어난다. 우리는 악수가 완벽하다는 것을 모든 사람의 팔이 교차되지 않았을 때 완벽하다고 한다.

N이 주어지면 완벽한 악수의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다.

출력

완벽한 악수의 경우의 수를 987654321로 나눈 나머지를 출력한다.

예제 입력

4

예제 출력

2

힌트

출처