시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 26 16 11 57.895%

문제

정 N각형의 꼭지점에서 다른 꼭지점을 잇는 선분을 그으면 주어진 다각형을 삼각형이나 사각형으로 나눌 수 있다. 이와 같은 선분들은 교차해서는 안된다. N이 주어졌을 때, 가능한 삼각분할의 경우의 수와 사각분할의 경우의 수를 구하는 프로그램을 작성하시오. 회전, 또는 대칭을 이용한 경우에는 같은 것으로 세지 않고 다른 것으로 센다.

입력

첫째 줄에 N(1≤N≤1,000)이 주어진다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.

출력

첫째 줄에 삼각 분할의 경우의 수를, 둘째 줄에 사각 분할의 경우의 수를 출력한다.

예제 입력

6

예제 출력

14
3

힌트