题目描述

已知有$\red{n}$本书（从$\red{1～n}$编号）和$\red{n}$个人（从$\red{1～n}$编号），每个人都有一个自己喜爱的书的列表，现在请你编写一个程序，设计一种分书方案，使得每个人都能获得一本书，且这本书一定要在他的喜爱列表中。

输入格式

输入数据共若干行，第一行为一个正整数$\red{n（n <= 20）}$，从第$\red{2}$行到第$\red{n+1}$行，每行有$\red{n}$个$\red{0}$或$\red{1}$组成，第$\red{k}$行表示编号为$\red{k-1}$的人对这$\red{n}$本书的喜好列表，$\red{0}$表示不喜欢，$\red{1}$表示喜欢。

输出格式

输出数据仅一个整数，表示符合条件的分配方案的总数。

样例

输入数据

3
001
010
100

输出数据

1

提示

数据范围与提示

对于 $\red{100\%}$ 的数据，$\red{n <= 20}$