쿄코는 생일 선물로 엄청나게 큰 케이크를 받았다.
보통 원형 케이크와는 다르게, 그 케이크는 N개 (4<=N<=5,000, N은 짝수) 의 꼭짓점을 가지는 N각형이다. 아무리 먹성이 좋은 쿄코였지만, 그만한 케이크를 다 먹을 수는 없었기 때문에, 그녀는 그 케이크를 사각형들로 나누어 친구들과 함께 먹기로 하였다.
친구들이 학교를 간 사이에 케이크를 자르려던 그녀는 갑자기 이 케이크를 사각형으로 자를 수 있는 방법의 수는 몇 가지가 있는지 궁금해졌다. 방법의 수를 세던 그녀는 손가락이 10개밖에 없었기 때문에 한계에 부딪혔고, 궁금증을 해소할 수 없었던 그녀는 우리에게 부탁을 해왔다.
그녀의 궁금증을 해소하기 위해 방법의 수를 구해보자. 가짓수가 상당히 크므로 1,000,000,000 로 나눈 값을 출력하도록 하자.
단, 케이크를 자를 때는 꼭짓점과 꼭짓점을 잇는 직선 모양으로 잘라야 하며, 교차하게 자를 수 없다. 자르는 방법이 다르면 모양은 같아도 다른 방법으로 간주한다.
입력 4 출력 1 입력 6 출력 3 입력 8 출력 12
출처:IOI 계절학교(문제의 범위를 늘림) 추천:kudoshiho