题目描述

众所不知，rly 现在不会玩国际象棋。但是，作为一个 OIer，rly 当然做过八皇后问题。这里再啰嗦几句，皇后可以攻击到同行同列同对角线，在 $n\times n$ 的方格中摆 $n$ 个皇后使其互不攻击到，求不同的解的数量，这就是经典的 $n$ 皇后问题。现在问题推广到 $n$ 皇后问题，这个问题对于你而言实在是小菜一叠。但因为上一次 rly 把棋盘弄破了，又拿不出新的，所以 rly 打算难一点点，问题就是破棋盘上的 $n$ 皇后问题。他想知道……（你们懂的）。

棋子都是相同的。

输入格式

一行，一个正整数 $n$。

接下来 $n$ 行，每行 $n$ 个数，要么为 $0$，表示没坏，要么 $1$，表示坏了。

输出格式

一行，输出不同的解的数量。

样例输入

4
1 0 1 1
1 1 1 0
0 1 1 1
1 1 0 1

样例输出

1

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 20$。

题目来源

By FancyCoder