다각형의 분할

정 N각형의 꼭짓점을 서로 잇는 선분을 그어 다각형을 분할하려고 한다. 모든 조각이 삼각형이 되도록 분할하는 방법의 수와, 모든 조각이 사각형이 되도록 분할하는 방법의 수를 각각 구하시오.

그은 선분들은 서로 교차해서는 안 된다. 회전하거나 뒤집어서 같은 모양이 되는 경우도 서로 다른 경우로 센다.

첫째 줄에 정수 N이 주어진다.

• 3 <= N <= 1,000

답이 매우 커질 수 있으므로 각 값을 1,000,000,000으로 나눈 나머지를 출력한다.

첫째 줄에 삼각형으로만 분할하는 방법의 수를 출력한다. 둘째 줄에 사각형으로만 분할하는 방법의 수를 출력한다.