点击此处下载样例文件

题目描述

有一个 N×N 的棋盘，让你放 N 个皇后，同一行只能放一个，同一列也只能放一个。但是棋盘上有 N 个坏格子是不能放皇后的，同一行有且仅有一个坏格子，同一列也有且仅有一个坏格子。

所有的皇后都视为相同的棋子。

问：你有多少种放法？

输入格式

第一行：一个整数 N

接下来是一个 N×N 的 01 矩阵 A，同一行的数之间以一个空格隔开，其中 Aij=1 表示第 i 行第 j 列的格子是坏格子。输入数据保证满足题目条件。

输出格式

一个整数，表示答案。

样例输入

3
0 0 1
1 0 0
0 1 0

样例输出

2

数据范围

100% 的数据：1 ≤ N ≤ 200