31910번 - 이진수 격자 서브태스크

각 칸에 $0$ 또는 $1$이 적혀 있는 $N \times N$ 격자가 있다. 인선이는 $1$행 $1$열에서 출발해 $N$행 $N$열까지 이동하는데, 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다. 인선이는 어떤 칸에 방문할 때마다 그 칸에 적힌 문자를 자신이 갖고 있는 문자열의 뒷부분에 덧붙인다. 예를 들어, 주어진 그림에서 인선이가 $1$행 $1$열에서 출발하여 순서대로 오른쪽, 아래, 오른쪽으로 한 칸씩 이동한다면 인선이가 가진 문자열은 1101이다.

$N$행 $N$열에 도착하면 인선이는 자신이 갖고 있는 문자열을 이진수로 해석한 값 $M$을 계산한다. 예를 들어, 인선이가 가진 문자열이 1101일 경우 $M=13$이다. 인선이가 계산하게 될 $M$의 최댓값을 구하시오.

첫째 줄에 격자의 크기를 의미하는 정수 $N$이 주어진다. $(2 \leq N \leq 30)$

둘째 줄부터 $N$개의 줄에 걸쳐 한 줄에 $N$개의 정수가 공백으로 구분되어 주어진다. 이 정수는 반드시 $0$ 또는 $1$이다. $(i+1)$번째 줄에 주어진 $j$번째 수는 $i$행 $j$열에 적힌 격자의 칸에 적힌 수를 의미한다.

$M$의 최댓값을 출력한다. 정답이 32비트 정수 범위를 넘을 수 있음에 주의하시오.