이진수 격자

각 칸에 $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비트 정수 범위를 넘을 수 있으니 주의하시오.