시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 1024 MB 27 13 8 53.333%

문제

순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 지상에는 총 $N^2$ 개의 성지가 있다. 이 성지들은 $N \times N$ 격자 모양으로 배치가 되어있으며, 위쪽에서 $i$번째, 왼쪽에서 $j$번째 성지를 $(i, j)$번 성지라고 한다. 성지에 도착한 순례자는 흑색 시련백색 시련 둘 중 하나를 반드시 받게 된다. 흑색 시련이란 본인의 업을 치르게 되는 "카르마에 의한 시련"이고, 백색 시련은 본인의 격을 높이기 위한 "상승을 위한 시련"이다.

순례자는 "현세"를 뜻하는 $(1, 1)$번 성지에서 시련을 받는 것으로 순례를 시작한다. $(i, j)$번 성지의 시련을 받은 순례자는 $(i+1, j)$번 성지와 $(i, j+1)$번 성지 중 하나로 이동하여 시련을 계속 받는 것을 반복한다. 그렇게 "해탈"을 뜻하는 $(N, N)$번 성지에 도달하여 마지막 시련을 받아, 총 $2N-1$ 개의 성지를 방문한 한 번의 순례가 끝난다.

이런 방식으로 총 $\binom{2N-2}{N-1}$가지의 서로 다른 순례를 할 수 있다. 그렇게 순례자는 해탈의 경지에 도달하기 위하여, 모든 방식의 순례를 정확히 한 번씩 시행했다.

모든 순례가 끝나 잠시 쉬고 있는 순례자는 이번 순례의 기억을 되새기고 있다. 순례자의 기억은 순례자가 순례 중 이동할 수 있는 가능성이 있는 순서대로 한 개 이상의 성지를 나열한 것이다. 정확히 말해서, $l$ 개의 성지 $(i_1,j_1)$, $(i_2,j_2)$, $\cdots$, $(i_l,j_l)$로 이루어진 기억은, $i_1 \le i_2 \le \cdots \le i_l$, $j_1 \le j_2 \le \cdots \le j_l$, $(i_{k-1},j_{k-1})\neq(i_k,j_k)$ ($2 \leq k \le l$)의 모든 조건을 만족해야 한다.

예를 들면, $N=2$일 때, 순례자가 떠올릴 수 있는 기억은 다음과 같이 총 $4 + 5 + 2 = 11$가지가 있다.

 


 

자애롭고 전지전능하신 신께서는 이 모든 것을 지켜보았고, 큰 감명을 받았다. 신은 어떤 성지에서 시련을 받았느냐보다도 어떤 시련을 받았느냐를 더 중요히 여기기 때문에, 순례자의 기억에 등장하는 성지를 모두 그 성지에 대응되는 시련으로 바꿔 인식한다. 신은 순례자의 기억을 모두 보고 나서, 한 번 이상 등장하는 기억에 대해, 이 기억이 총 $X$번 등장한다면 $X^2+1$만큼 감명받는다. 이렇게 신이 감명하는 정도의 총합을 구하여라.

입력

첫 번째 줄에, 격자의 크기를 의미하는 자연수 $N$이 주어진다.

다음 $N$ 개의 줄의 $i$ 번째 줄에, 길이 $N$의 01로만 구성된 문자열이 주어진다. $j$번째 문자가 0이라는 것은, $(i, j)$번 성지에서 흑색 시련을 받는다는 것을 의미하고, 1이라는 것은 $(i, j)$번 성지에서 백색 시련을 받는다는 것을 의미한다.

출력

첫 번째 줄에, 신이 감명하는 정도를 구하여 $10^9+7$로 나눈 나머지를 출력한다.

서브태스크 1 (1점)

  • $2 \le N \le 5$

서브태스크 2 (10점)

  •  $2 \le N \le 10$

서브태스크 3 (100점)

  • $2 \le N \le 20$

예제 입력 1

2
00
00

예제 출력 1

48

첫째 예제에서, 신이 인식하는 순례자의 기억은 0, 00, 000의 세 가지다. 이 중 0은 네 번, 00은 다섯 번, 000은 두 번 등장하기 때문에, 답은 $(4^2+1) + (5^2+1) + (2^2+1) = 48$이다.

 


 

예제 입력 2

2
00
10

예제 출력 2

30

둘째 예제에서, 신이 인식하는 순례자의 기억은 0, 1, 00, 01, 10, 000, 010의 일곱 가지다. 이 중 0, 00만 세 번 등장하고, 나머지는 모두 한 번 등장하기 때문에, 답은 $2 \times (3^2+1) + 5 \times (1^2+1) = 30$이다.

 


 

예제 입력 3

5
11010
00110
10110
10110
10111

예제 출력 3

1304460

출처

Contest > 전시관 > 제1 전시관 4번

채점

  • 예제는 채점하지 않는다.