有一个形状为$n \times n$矩形的迷宫，入口和出口依次位于左上角和右上角。

请编程找出所有在迷宫中从入口（左上角）到出口（右上角）的不重复路径，并输出路径总数。

处于迷宫中时，可选择周围八个方向行走。当前进方格中数字为0时，表示可通过；数字为1时，表示不可通过。

输入格式

第$1$行有一个整数$n$，表示迷宫的大小。

第$2$到$n+1$行，每行有$n$个数字，表示迷宫中的数字。数据保证入口与出口的数字不为$1$。

输出格式

输出$1$行一个整数，表示从出口到入口的路径总数。

样例

输入样例1

3
0 0 0
0 1 1
1 0 0

输出样例1

2

输入样例2

3
0 1 0
1 1 0
0 0 0

输出样例2

0

数据范围与提示

• 对于100%的数据，$n \leq 5$。
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$256000\mathrm{KB}$