题目描述

一个 $N\times N$ 的迷宫方格，在方格内 0 表示可以走，1 表示不能行走，2 表示宝藏。

现在从左上角 $(1,1)$ 的位置进入迷宫寻找宝藏。统计有多少条线路可以找到宝藏（每条线路经过的格子只能访问 $1$ 次）。

注意：第一个格子不为 $1$。

输入格式

第一行一个正整数 $N$

接下来输入 $N\times N$ 行由 0，1，2 组成的矩阵。

输出格式

一行，一个整数，表示可以找到宝藏的线路。

2
0 0
0 2

2

样例 1 解释

1 : (1,1) -> (1,2) -> (2,2)

2 : (1,1) -> (2,1) -> (2,2)

5
0 0 1 1 0
1 0 0 0 0
0 0 0 0 2
0 1 1 0 0
0 0 0 1 0

12

数据规模与约定

对于 $100\%$ 的数据，$3 \le n \le 10$。