谁是19王

题目描述

有一天，YangHui 和秋月为了争夺飞梦自救群19王的称号，展开了一场对弈。

规则很简单：二人面对一个 $n\times n$ 的棋盘，每次每人需落 $n$ 个子，但这 $n$ 个子必须彼此不同行不同列，否则就出局。

比赛开始，YangHui 率先落下了 $n$ 个棋子，而一边看热闹的 aikx 突然想知道秋月的下一手棋一共有多少种不同落子的方法。

答案可能很大，请对质数 $1,000,000,007$ 取模。

输入

第一行，一个正整数 $n$，表示棋盘的大小。

接下来 $n$ 行，每行 $n$ 个数字，其中1代表该位置已落子，0代表未落子。

输出

一个整数，代表答案。

输入样例

3
1 0 0
0 1 0
0 0 1

输出样例

2

数据范围

对于$50\%$的数据，$n\le10$;

对于$80\%$的数据，$n \le 100$;

对于$100\%$的数据，$n \le 1000$.

AUTHOR: aikx