# Appreciation

/*
 * Problem :: 17070 / 파이프 옮기기 1
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 파이프 한쪽 끝을 (N,N)으로 이동시키는 방법의 수를 구하는데 있어
 *   파이프 한쪽 끝을 (N,N-1) 혹은 그 이전의 다른 좌표로 이동시키는 방법의 수가 도움이 되는가?
 *   + 그렇습니다 => DP 로 풀자
 *
 * - 파이프 기준 오른쪽에 위치한 파이프 한쪽 끝과
 *   파이프의 현재 상태가 '가로', '세로', '대각선' 인지 알면
 *   새 집에서 파이프가 어디 위치해있는지 특정지을 수 있다
 *
 * - 가로 - R, 세로 - C, 대각선 - D 라고 하면,
 *   dp[i][j][R] - 파이프 오른쪽 끝이 (i,j) 칸에 가로로 놓이게끔 이동시키는 방법의 수
 *   dp[i][j][C] - 파이프 오른쪽 끝이 (i,j) 칸에 세로로 놓이게끔 이동시키는 방법의 수
 *   dp[i][j][D] - 파이프 오른쪽 끝이 (i,j) 칸에 대각선으로 놓이게끔 이동시키는 방법의 수
 *   + 점화식을 세울 수 있다
 *     # 가로
 *       dp[i][j][R] += dp[i][j-1][R] / (i,j-1) 가로 -> (i,j) 가로
 *       dp[i][j][R] += dp[i][j-1][D] / (i,j-1) 대각선 -> (i,j) 가로
 *     # 세로
 *       dp[i][j][C] += dp[i-1][j][C] / (i-1,j) 세로 -> (i,j) 세로
 *       dp[i][j][C] += dp[i-1][j][D] / (i-1,j) 대각선 -> (i,j) 세로
 *     # 대각선
 *       dp[i][j][D] += dp[i-1][j-1][R] / (i-1,j-1) 가로 -> (i,j) 대각선
 *       dp[i][j][D] += dp[i-1][j-1][C] / (i-1,j-1) 세로 -> (i,j) 대각선
 *       dp[i][j][D] += dp[i-1][j-1][D] / (i-1,j-1) 대각선 -> (i,j) 대각선
 *
 * Point
 * - dp[1][2][R] = 1 로 시작한다
 *   + i=1, j=3~N
 *     i=2, j=1~N
 *     i=3, j=1~N
 *     ...
 *     이렇게 순회해야 하는데
 *     i=1 일때 예외처리하기가 좀 껄끄럽다
 *     # 그래서 dp 를 모두 0 으로 초기화시켜주고
 *       =(할당연산자) 가 아닌 +=(대입연산자) 를 사용했다
 *       -> 더하는 칸이 벽칸이나 도달하기 불가능한 칸이면 더해지는 방법의 수는 0일 테니
 *          += 를 쓰면 위와같은 예외를 따로 처리하지 않을 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
enum Status { R, C, D };

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    bool isWall[N+1][N+1];
    memset(isWall, false, sizeof(isWall));
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            cin >> isWall[i][j];
        }
    }

    // Process
    int dp[N+1][N+1][3];
    memset(dp, 0, sizeof(dp));
    dp[1][2][R] = 1; /* 초기화 */
    /* dp[i][j][R] - 파이프 오른쪽 끝이 (i,j) 칸에 가로로 놓이게끔 이동시키는 방법의 수
     * dp[i][j][C] - 파이프 오른쪽 끝이 (i,j) 칸에 세로로 놓이게끔 이동시키는 방법의 수
     * dp[i][j][D] - 파이프 오른쪽 끝이 (i,j) 칸에 대각선으로 놓이게끔 이동시키는 방법의 수 */
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            if (not(isWall[i][j])) {
                dp[i][j][R] += dp[i][j-1][R]; /* (i,j-1) 가로 -> (i,j) 가로 */
                dp[i][j][R] += dp[i][j-1][D]; /* (i,j-1) 대각 -> (i,j) 가로 */
                
                dp[i][j][C] += dp[i-1][j][C]; /* (i-1,j) 세로 -> (i,j) 세로 */
                dp[i][j][C] += dp[i-1][j][D]; /* (i-1,j) 대각 -> (i,j) 세로 */
                
                if (not(isWall[i-1][j]) && not(isWall[i][j-1])) {
                    dp[i][j][D] += dp[i-1][j-1][R]; /* (i-1,j-1) 대각 -> (i,j) 가로 */
                    dp[i][j][D] += dp[i-1][j-1][C]; /* (i-1,j-1) 대각 -> (i,j) 세로 */
                    dp[i][j][D] += dp[i-1][j-1][D]; /* (i-1,j-1) 대각 -> (i,j) 대각 */
                }
            }
        }
    }

    // Control : Output
    cout << dp[N][N][R] + dp[N][N][C] + dp[N][N][D] << endl;
}

// Helper Functions
/* None */