정상 회담 2
시간 제한2초메모리 제한128 MB
원탁에 앉은 N명의 대표가 손을 맞잡을 때 선분이 서로 교차하지 않는 짝짓기 방법의 수를 987654321로 나눈 나머지로 구합니다.
문제
여러 소국가로 나뉘어 있던 A국을 다시 하나로 합치기 위해 각 소국가의 대표 N명이 원탁에 모였다.
각 대표는 회의 전에 서로 악수를 하려 한다. 자리는 미리 정해져 있으며, 각 대표는 정확히 한 사람과만 악수할 수 있다. 모든 악수는 동시에 이루어진다.
악수하는 두 사람을 잇는 선분을 원탁 안쪽에 그렸을 때 어떤 두 선분도 서로 교차하지 않으면, 모든 대표가 완벽하게 악수했다고 한다.
N이 주어졌을 때 완벽하게 악수하는 경우의 수를 구하시오.
입력
첫째 줄에 회담에 참가한 사람의 수 N이 주어진다. N은 10,000 이하의 짝수이다.
출력
완벽한 악수의 경우의 수를 987654321로 나눈 나머지를 출력한다.