다각형의 분할
시간 제한2초메모리 제한128 MB
정N각형을 대각선으로 교차 없이 모두 삼각형이나 모두 사각형으로 나누는 방법의 수를 1,000,000,000으로 나눈 나머지로 구합니다.
문제
정 N각형의 꼭짓점을 서로 잇는 선분을 그어 다각형을 분할하려고 한다. 모든 조각이 삼각형이 되도록 분할하는 방법의 수와, 모든 조각이 사각형이 되도록 분할하는 방법의 수를 각각 구하시오.
그은 선분들은 서로 교차해서는 안 된다. 회전하거나 뒤집어서 같은 모양이 되는 경우도 서로 다른 경우로 센다.
입력
첫째 줄에 정수 N이 주어진다.
- 3 <= N <= 1,000
답이 매우 커질 수 있으므로 각 값을 1,000,000,000으로 나눈 나머지를 출력한다.
출력
첫째 줄에 삼각형으로만 분할하는 방법의 수를 출력한다. 둘째 줄에 사각형으로만 분할하는 방법의 수를 출력한다.