Informatica Online Judge

  학교가기1 (Large) [0705 / 02C1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 112   Total Tried : 139


The Champion of this Problem (C++) : gs19099 - 0ms / 434byte
My Best Submission (C++) : N/A

[]

Background

경곽이가 사는 동내는 도로설계가 잘 되어 있어 모두 직각인 도로로 구성된 마을이다.

경곽이의 집은 (1,1), 학교는 (n,n)에 위치한다.

경곽이는 학교까지 항상 최단경로로 이동한다.

마을의 한 블럭의 길이는 1이다.

그런데 어느날 학교가는 도로들 중 일부도로들이 공사를 하기 시작했다.

도로에 0으로 표시된 곳은 공사를 하는 곳으로 이동할 수 없다.

만약 n이 3이고 도로의 정보가 다음과 같다면

1 0 0
1 1 1
1 0 1

집에서 학교까지 이동할 수 있는 모든 방법은 한 가지 뿐이다.

(1,1) (2,1) (2,2) (2,3) (3,3) 으로 이동하는 길이 유일하다.

도로의 크기 n과 도로의 정보가 주어질 때, 학교까지 총 이동가능한 방법을 구하는 프로그램을 작성하시오.

Input

첫 줄에 입력크기 n이 입력된다.
다음 줄 부터 n줄에 걸쳐서 n개씩 도로의 정보가 탭으로 구분하여 입력된다.

* 단 n은 300 이하의 자연수

Output

모든 경우의 수를 10억7로 나눈 나머지를 출력한다. 만약 경로가 없다면 -1을 출력한다.

IO Example

입력
3
1 0 0
1 1 1
1 0 1

출력
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]