시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3521288833.588%

문제

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

입력

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

출력

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

예제 입력 1

6

예제 출력 1

14
3