题目描述

设有一个$N\times N$方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放$0$和$1$，$0$表示可通，$1$表示不能，入口和出口处肯定是$0$。迷宫走的规则如下所示：即从某点开始，有八个方向可走，前进方格中数字为$0$时表示可通过，为 $1$时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径(不能重复)。

输入格式

一个正整数$N$。

输出格式

输出路径总数，如果无法到达，则输出$0$。

样例

3 
0 0 0 
0 1 1 
1 0 0

2

数据规模与约定

对于$100\%$的数据：$2\le N\le 10$。