给定一个M*M(2≤M≤9)的迷宫，迷宫用0表示通路，1表示围墙。

迷宫的入口和出口分别位于左上角和右上角，入口和出口显然都是0。

在迷宫中移动可以沿着上、下、左、右、左上、右上、左下、右下八个方向进行，前进格子中数字为0时表示可以通过，为1时表示围墙不可通过，需要另外再找找路径。

请统计入口到出口的所有路径（不重复），并输出路径总数。若从入口无法到达出口，请输出0。

第一行输入1个正整数M(≤M≤9)，表示迷宫是M行M列。

第2行到第n+1行是一个M阶的0-1方阵。

统计入口到出口的所有路径（不重复），并输出路径总数。若从入口无法到达出口，请输出0。