18345번 - 순례자의 기억과 감명받은 신 서브태스크

순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 지상에는 총 $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$의 0과 1로만 구성된 문자열이 주어진다. $j$번째 문자가 0이라는 것은, $(i, j)$번 성지에서 흑색 시련을 받는다는 것을 의미하고, 1이라는 것은 $(i, j)$번 성지에서 백색 시련을 받는다는 것을 의미한다.

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

• $2 \le N \le 5$

•  $2 \le N \le 10$

• $2 \le N \le 20$