每个人戴不同帽子的方案数

题目描述

总共有 $n$ 个人和 $40$ 种不同的帽子，帽子编号从 $1$ 到 $40$ 。

给你一个整数列表的列表 $hats$ ，其中 $hats[i]$ 是第 $i$ 个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。

由于答案可能很大，请返回它对 $10^9 + 7$ 取余后的结果。

输入格式

第一行一个整数 $n$，表示人数；

接下来 $n$ 行，每行第一个数表示第 $i$ 个人喜欢帽子列表的长度 $len_i$，接下来是空格分开的 $len_i$ 个整数。

输出格式

一行一个整数表示答案。

示例 1：

3
2 3 4
2 4 5
1 5

1

解释: 给定条件下只有一种方法选择帽子。

第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。

示例 2：

2
3 3 5 1
2 3 5

4

解释: 总共有 4 种安排帽子的方法：

(3,5)，(5,3)，(1,3) 和 (1,5)

示例 3：

4
4 1 2 3 4
4 1 2 3 4
4 1 2 3 4
4 1 2 3 4

24

解释: 每个人都可以从编号为 1 到 4 的帽子中选。

(1,2,3,4) 4 个帽子的排列方案数为 24 。

提示：

• $n == hats.length$
• $1 <= n <= 10$
• $1 <= hats[i].length <= 40$
• $1 <= hats[i][j] <= 40$
• $hats[i]$ 包含一个数字互不相同的整数列表。

SOURCE

每个人戴不同帽子的方案数