프로그램 명: boi_points
제한시간: 1 초
3 행 N 열의 점이 주어질 때 다음을 만족하는 다각형의 개수를 구하라.
- 모든 점을 포함하면서
- 인접한 점들로 연결
- 꼬이지 않게
이웃 하다는 것은 그림 1 에 주어져 있다.
그림 2 는 N = 6 인 경우의 가능한 경우 두 가지이다.
입력
정수 N 이 주어진다.(N ≤ 1,000,000,000).
출력
구한 답을 1,000,000,000 로 나눈 나머지를 출력한다.
입출력 예
입력
3
출력
8
입력
4
출력
40
출처:boi 2007 Germany
[질/답]
[제출 현황]
[푼 후(0)]