순례자의 기억과 감명받은 신

순례자는 끝나지 않을 것처럼 보이는 순례를 계속하고 있다. 지상에는 $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$, 그리고 $2 \le k \le l$인 모든 $k$에 대해 $(i_{k-1},j_{k-1}) \neq (i_k,j_k)$이다.

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

자애롭고 전지전능한 신은 이 모든 것을 지켜보았고 큰 감명을 받았다. 신은 성지 자체보다 어떤 시련을 받았는지를 더 중요하게 여긴다. 그래서 신은 순례자의 기억에 등장하는 성지를 모두 그 자리에서 받은 시련으로 바꿔 인식한다. 신은 순례자의 기억을 모두 본 뒤, 한 번 이상 등장한 기억마다 그 기억이 총 $X$번 등장한다면 $X^2+1$만큼 감명받는다. 신이 감명받는 정도의 총합을 구하라.

첫 번째 줄에 격자의 크기를 나타내는 자연수 $N$이 주어진다.

다음 $N$개의 줄 중 $i$번째 줄에는 길이 $N$이고 0과 1로만 이루어진 문자열이 주어진다. $j$번째 문자가 0이면 $(i, j)$번 성지에서 흑색 시련을 받는다는 뜻이고, 1이면 백색 시련을 받는다는 뜻이다.

첫 번째 줄에 신이 감명받는 정도의 총합을 $10^9+7$로 나눈 나머지를 출력한다.