프로그램 명: ball-paint
제한시간: 1 초
[요약]
2N 개의 흰공이 테이블위에 두 행으로 놓여져 있다. 2 * N 모양의 직사각형을 유지하면서.
존은 검은 페인트 통을 가지고 있다.(왜?? 라고 묻지 마라^^)
그는 모든 공을 검은색으로 칠하기를 원한다.
그러나 이 일을 하면서 재미나는 수학 게임을 하고자 한다.
(이것도 왜 라고 묻지마라)
처음 , 그는 모든 공을 검은색으로 칠할수 있는 다른 방법의 수를 계산한다.
얼마지 않아,
그는 방법의 수는 (2N)! 라는 것을 알았다. 이 것은 매우 쉬운일이라는 것을 알았다.
그래서 그는 이 문제를 조금 더 재미나게 만들 규칙을 생각했다.
-
존이 칠한 첫번째 공은 2N 개의 공 중에 하나 일 수 있다.
-
그 후에 ,
그가 칠한 다음 공은 그가 이미 칠한 검은 공과 인접해야 한다.
수평 , 수직, 대각선으로 인접해 있으면 인접하다고 한다.
이 규칙으로 공을 색칠할 때 칠할 수 있는 방법의 수를 구하는 것이 문제이다.
There are 2N white balls on a table in two rows, making a nice 2-by-N rectangle. Jon has a big paint bucket
full of black paint. (Don’t ask why.) He wants to paint all the balls black, but he would like to have some
math fun while doing it. (Again, don’t ask why.) First, he computed the number of different ways to paint
all the balls black. In no time, he figured out that the answer is (2N)! and thought it was too easy. So, he
introduced some rules to make the problem more interesting.
- The first ball that Jon paints can be any one of the 2N balls.
- After that, each subsequent ball he paints must be adjacent to some black ball (that was already
painted). Two balls are assumed to be adjacent if they are next to each other horizontally, vertically,
or diagonally.
Jon was quite satisfied with the rules, so he started counting the number of ways to paint all the balls
according to them. Can you write a program to find the answer faster than Jon?
입력
Each test case consists of a single line containing an integer N, where 1 ≤ N ≤ 1,000.
출력
print out a single line that contains the number of possible ways that Jon can paint all
the 2N balls according to his rules. The number can become very big, so print out the number modulo
1,000,000,007.
입출력 예
입력
1
출력
2
입력
2
출력
24
입력
3
출력
480
출처:standford/2011/
[질/답]
[제출 현황]
[푼 후(0)]