分书问题

题目描述

现有 n 本书（编号 1 到 n ）和 n 个人（编号 1 到 n ）。每个人都有一个自己喜欢的书的列表（用 0/1 表示）。请你计算有多少种不同的分配方案，使得每个人都能恰好分到一本书，且这本书必须在该人喜欢的列表中。

输入

• 第一行包含一个整数 n （ 1 \le n \le 20 ），表示书和人的数量。
• 接下来 n 行，每行包含一个长度为 n 的 01 字符串，第 i 行表示第 i 个人对 n 本书的喜好情况：第 j 个字符为 1 表示喜欢第 j 本书，为 0 表示不喜欢。

输出

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

样例

提示

数据范围与约定

• 1 \le n \le 20
• 输入保证每位同学至少喜欢一本书，且总存在至少一种合法分配方案。

来源

课课通