有 $n$ 本互不相同的书和 $n$ 个人，书与人均编号为 $1$～$n$。每个人都有自己喜欢的书籍列表。

需要让每个人恰好获得一本书，每本书也恰好分给一人，并且每个人拿到的书必须在他的喜欢列表中。请计算符合要求的分配方案总数。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行是一个长度为 $n$ 的 0/1 字符串。第 $i$ 行第 $j$ 个字符为 1 表示第 $i$ 个人喜欢第 $j$ 本书，为 0 表示不喜欢。

输出格式

输出符合要求的分配方案总数。

5
00110
11001
01100
00010
01001

1

1
1

1

2
00
10

0

数据范围

$1\le n\le15$。