미팅의 저주
시간 제한1초메모리 제한256 MB
원탁에 둘러앉은 N명이 서로 짝을 지어 동시에 악수할 때 팔이 엇갈리지 않는 경우의 수를 987654321로 나눈 나머지를 구한다.
문제
인하대 컴퓨터공학과에 재학 중인 이산이는 오랜만에 미팅을 나가려 한다. 미팅은 N명이 원탁에 앉아 진행된다. 질투가 난 이산이의 친구 명기는 X의 저주를 걸었다. 그 저주는 N명이 동시에 2명씩 짝을 지어 악수할 때 팔이 교차하거나 악수를 하지 못한 사람이 한 명이라도 있으면 미팅이 실패하게 되는 저주다. 명기는 이산이에게 저주를 풀 기회를 주었다. 미팅에 성공하는 경우의 수를 구해 큰소리로 외치면 저주가 풀린다. 이산이는 계산 능력이 부족해 당신에게 도움을 청했다. 이산이가 걸린 저주를 풀어주는 프로그램을 만들자.
미팅에 참가한 사람이 4명일 때 미팅에 성공하는 경우는 다음 그림과 같이 2가지이다.
미팅에 참가한 사람이 6명일 때 미팅에 성공하는 경우는 다음 그림과 같이 5가지이다.
입력
첫째 줄에 미팅에 참가하는 사람의 수 N이 주어진다. 이 값은 10,000 이하의 짝수이다.
출력
미팅에 성공하는 경우의 수를 987654321로 나눈 나머지를 출력한다.