There are n people and 40 types of hats labeled from 1 to 40.
Given a list of list of integers hats, where hats[i] is a list of all hats preferred by the i-th person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.
Example 2:
Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats
(3,5), (5,3), (1,3) and (1,5)

Example 3:
Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

Example 4:
Input: hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
Output: 111

 
Constraints:

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.

Difficulty: MEDIUM
Tags: Dynamic programming

Bit manipulation

Data structures
Skill types: Dynamic programming

Bit manipulation

Data structures

Starter code:
class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		n = len(hats)
		dic = collections.defaultdict(list)
		for (i, hat) in enumerate(hats):
			for h in hat:
				dic[h].append(i)
		bfs = {0: 1}
		target = (1 << n) - 1
		res = 0
		for h in range(1, 41):
			new_bfs = bfs.copy()
			for p in dic[h]:
				for (mask, cnt) in list(bfs.items()):
					new_mask = 1 << p | mask
					if new_mask != mask:
						if new_mask not in new_bfs:
							new_bfs[new_mask] = 0
						new_bfs[new_mask] += cnt
			bfs = new_bfs
		return bfs[target] % (10 ** 9 + 7) if target in bfs else 0


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		MOD = int(1000000000.0) + 7
		n = len(hats)
		d = {0: 1}
		rev = [[] for _ in range(41)]
		for (i, h) in enumerate(hats):
			for e in h:
				rev[e].append(i)
		for i in range(40):
			r = rev[i + 1]
			nx = d.copy()
			for j in d:
				for k in r:
					if not j & 1 << k:
						nj = j | 1 << k
						nx[nj] = nx.get(nj, 0) + d[j]
			d = nx
		return d.get((1 << n) - 1, 0) % MOD


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:

		def helper(hat, assignedPeople):
			if assignedPeople == target_state:
				return 1
			if hat > 40:
				return 0
			if dp[hat][assignedPeople] is not None:
				return dp[hat][assignedPeople]
			res = 0
			res += helper(hat + 1, assignedPeople)
			for person in hat2person[hat]:
				if assignedPeople & 1 << person != 0:
					continue
				res += helper(hat + 1, assignedPeople | 1 << person)
			dp[hat][assignedPeople] = res
			return dp[hat][assignedPeople]
		n = len(hats)
		M = 10 ** 9 + 7
		hat2person = [[] for _ in range(41)]
		for i in range(n):
			for hat in hats[i]:
				hat2person[hat].append(i)
		target_state = (1 << n) - 1
		dp = [[None for j in range(1 << n)] for i in range(41)]
		return helper(1, 0) % M


import functools as ft

class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		const = 10 ** 9 + 7
		cache = {}
		matr = [[False] * 10 for i in range(40)]
		maxx = -1
		for j in range(len(hats)):
			for i in hats[j]:
				matr[i - 1][j] = True
				maxx = max(i - 1, maxx)

		def s(mask_p, h, n):
			if n == 0:
				return 1
			if h < 0 or n > h + 1:
				return 0
			c = str(mask_p + [h])
			if c in cache:
				return cache[c]
			res = s(mask_p, h - 1, n)
			for p in range(len(matr[h])):
				if mask_p[p] and matr[h][p]:
					mask_p[p] = False
					res += s(mask_p, h - 1, n - 1)
					mask_p[p] = True
			cache[c] = res
			return res
		mask_p = [True] * len(hats) + [False] * (10 - len(hats))
		return s(mask_p, maxx, len(hats)) % const


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		ownhat = {}
		n = len(hats)
		for i in range(n):
			hat = hats[i]
			for h in hat:
				if h in ownhat:
					ownhat[h].append(i)
				else:
					ownhat[h] = [i]
		dp = [[-1 for i in range(pow(2, n))] for i in range(41)]

		def dfs(ind, peoplemask, dp):
			if peoplemask == pow(2, n) - 1:
				return 1
			if ind > 40:
				return 0
			count = 0
			if dp[ind][peoplemask] != -1:
				return dp[ind][peoplemask]
			count = dfs(ind + 1, peoplemask, dp)
			if ind in ownhat:
				for people in ownhat[ind]:
					if peoplemask & pow(2, people) == 0:
						count = (count + dfs(ind + 1, peoplemask | pow(2, people), dp)) % (pow(10, 9) + 7)
			dp[ind][peoplemask] = count
			return count
		return dfs(1, 0, dp)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		h2p = defaultdict(list)
		n = len(hats)
		mod = 10 ** 9 + 7
		for (p, hat_list) in enumerate(hats):
			for h in hat_list:
				h2p[h].append(p)
		m = 1 << n
		dp = [[0] * m for _ in range(41)]
		dp[0][0] = 1
		for h in range(1, 41):
			for mask in range(m):
				dp[h][mask] = dp[h - 1][mask]
				for p in h2p[h]:
					if mask & 1 << p != 0:
						dp[h][mask] += dp[h - 1][mask ^ 1 << p]
		return dp[40][m - 1] % mod


import collections

class Solution(object):

	def numberWays(self, hats):
		lp = len(hats)
		mod = 10 ** 9 + 7
		h_dict = collections.defaultdict(set)
		for (i, h) in enumerate(hats):
			for val in h:
				h_dict[val].add(i)
		key_hats = list(h_dict.keys())
		lk = len(key_hats)

		@lru_cache(None)
		def arrange(idx, peo):
			if peo == (1 << lp) - 1:
				return 1
			if idx >= lk:
				return 0
			re = arrange(idx + 1, peo)
			for nt in h_dict[key_hats[idx]]:
				if peo & 1 << nt == 0:
					re += arrange(idx + 1, peo | 1 << nt)
			return re % mod
		return arrange(0, 0) % mod


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		h2p = defaultdict(list)
		for (i, hat) in enumerate(hats):
			for h in hat:
				h2p[h].append(i)
		n = len(hats)
		(dp, ndp) = (defaultdict(int), defaultdict(int))
		for hat in range(0, 41):
			for mask in range(1 << n):
				if mask == 0:
					ndp[mask] = 1
				else:
					ndp[mask] = dp[mask]
					for p in h2p[hat]:
						if mask & 1 << p:
							ndp[mask] += dp[mask ^ 1 << p]
							ndp[mask] %= 10 ** 9 + 7
			(dp, ndp) = (ndp, defaultdict(int))
		return dp[(1 << n) - 1]


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		n = len(hats)
		fullMask = (1 << n) - 1
		mp = defaultdict(list)
		for (idx, i) in enumerate(hats):
			for hat in i:
				mp[hat - 1].append(idx)
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def dp(hat, mask):
			if mask == fullMask:
				return 1
			if hat >= 40:
				return 0
			ans = dp(hat + 1, mask) % mod
			for person in mp[hat]:
				if not mask & 1 << person:
					ans += dp(hat + 1, mask ^ 1 << person)
					ans %= mod
			return ans % mod
		return dp(0, 0) % mod


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		hat_to_ppl = [[] for _ in range(41)]
		for (i, person) in enumerate(hats):
			for hat_preference in person:
				hat_to_ppl[hat_preference].append(i)
		hat_to_ppl = list([x for x in hat_to_ppl if x])
		num_hats = len(hat_to_ppl)
		num_ppl = len(hats)
		if num_hats < num_ppl:
			return 0

		@functools.lru_cache(None)
		def dp(i, mask):
			if i == num_hats:
				if bin(mask).count('1') == num_ppl:
					return 1
				else:
					return 0
			res = dp(i + 1, mask)
			for person in hat_to_ppl[i]:
				if mask & 1 << person == 0:
					mask |= 1 << person
					res += dp(i + 1, mask)
					mask ^= 1 << person
			return res % (10 ** 9 + 7)
		return dp(0, 0)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		(res, n, dp, hat2persons) = (0, len(hats), {}, collections.defaultdict(list))
		for (person, arr) in enumerate(hats):
			for hat in arr:
				hat2persons[hat - 1].append(person)
		dp[0] = 1
		for hat in range(40):
			dp_new = dict(dp)
			for person in hat2persons[hat]:
				for (state, cnt) in dp.items():
					if state & 1 << person == 0:
						if state | 1 << person not in dp_new:
							dp_new[state | 1 << person] = cnt
						else:
							dp_new[state | 1 << person] += cnt
			dp = dp_new
		print(dp)
		return dp[(1 << n) - 1] % (10 ** 9 + 7) if (1 << n) - 1 in dp else 0


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		hat_per_map = defaultdict(list)
		for (idx, i) in enumerate(hats):
			for j in i:
				hat_per_map[j - 1].append(idx)

		@lru_cache(None)
		def dp(hat, mask):
			if mask == (1 << len(hats)) - 1:
				return 1
			if hat >= 40:
				return 0
			ans = dp(hat + 1, mask) % 1000000007
			for i in hat_per_map[hat]:
				if not mask & 1 << i:
					ans += dp(hat + 1, mask | 1 << i) % 1000000007
			return ans
		return dp(0, 0) % 1000000007


from functools import lru_cache

class Solution:

	def numberWays(self, ppl_to_hats: List[List[int]]) -> int:
		hats_to_ppl = [[] for _ in range(41)]
		for (pid, hats) in enumerate(ppl_to_hats):
			for hid in hats:
				hats_to_ppl[hid].append(pid)
		num_ppl = len(ppl_to_hats)
		all_ppl_mask = (1 << num_ppl) - 1
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def helper(ppl_assigned_bitmask, next_hid):
			if ppl_assigned_bitmask == all_ppl_mask:
				return 1
			if next_hid > 40:
				return 0
			ways = helper(ppl_assigned_bitmask, next_hid + 1) % MOD
			for pid in hats_to_ppl[next_hid]:
				pid_mask = 1 << pid
				if pid_mask & ppl_assigned_bitmask == 0:
					ways += helper(pid_mask | ppl_assigned_bitmask, next_hid + 1)
					ways %= MOD
			return ways
		ret = helper(0, 1)
		return ret % MOD


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		from collections import defaultdict
		from functools import lru_cache
		ppl = defaultdict(list)
		for i in range(len(hats)):
			for j in hats[i]:
				ppl[j].append(i)

		@lru_cache(None)
		def call(ht, mask):
			if mask == (1 << len(hats)) - 1:
				return 1
			if ht > 40:
				return 0
			ans = call(ht + 1, mask)
			for p in ppl[ht + 1]:
				if mask & 1 << p:
					continue
				mask |= 1 << p
				ans += call(ht + 1, mask)
				mask ^= 1 << p
			return ans % (10 ** 9 + 7)
		return call(0, 0)


class Solution:

	def numberWays(self, hats) -> int:
		MOD = 10 ** 9 + 7
		n = len(hats)
		t = 1 << n
		people = [[] for _ in range(41)]
		for (i, hat) in enumerate(hats):
			for h in hat:
				people[h].append(i)
		dp = [[0 for _ in range(t)] for _ in range(41)]
		dp[0][0] = 1
		for i in range(1, 41):
			for mask in range(t):
				dp[i][mask] = dp[i - 1][mask]
				for p in people[i]:
					if mask & 1 << p > 0:
						dp[i][mask] = (dp[i][mask] + dp[i - 1][mask & ~(1 << p)]) % MOD
		ans = max((dp[i][t - 1] for i in range(40)))
		return dp[40][t - 1]


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		htop = [[] for i in range(41)]
		for (p, prefer_hats) in enumerate(hats):
			for h in prefer_hats:
				htop[h].append(p)
		htop = list([h for h in htop if h])
		(num_hats, num_people) = (len(htop), len(hats))
		if num_hats < num_people:
			return 0
		MOD = 10 ** 9 + 7

		@functools.lru_cache(None)
		def dp(i, mask):
			if bin(mask).count('1') == num_people:
				return 1
			if i == num_hats:
				return 0
			res = dp(i + 1, mask)
			for p in htop[i]:
				if mask & 1 << p == 0:
					mask |= 1 << p
					res += dp(i + 1, mask)
					mask ^= 1 << p
			return res % MOD
		return dp(0, 0)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		const = 10 ** 9 + 7
		matr = [0 for i in range(40)]
		maxx = -1
		used_h = set()
		for j in range(len(hats)):
			for i in hats[j]:
				matr[i - 1] += 2 ** j
				maxx = max(i - 1, maxx)
				used_h.add(i - 1)
		matr = matr[:maxx + 1]
		mask_p = 2 ** len(hats) - 1

		def s(mask_p, n, h, c_h, cache):
			if n > c_h:
				return 0
			if cache[mask_p][h] != None:
				return cache[mask_p][h]
			if mask_p == 0:
				return 1
			res = 0
			if h in used_h:
				c_h -= 1
				b = mask_p & matr[h]
				i = 0
				while b > 0:
					if b & 1:
						res += s(mask_p ^ 1 << i, n - 1, h - 1, c_h, cache)
					b = b >> 1
					i += 1
			res += s(mask_p, n, h - 1, c_h, cache)
			cache[mask_p][h] = res
			return cache[mask_p][h]
		return s(mask_p, len(hats), maxx, len(used_h), [[None] * (maxx + 1) for i in range(mask_p + 1)]) % const


class Solution:

	def numberWays(self, hats):
		ppl = len(hats)
		hats_to_ppl = [[] for i in range(41)]
		dp = [[-1 for j in range(2 ** ppl)] for i in range(41)]
		for i in range(ppl):
			for j in hats[i]:
				hats_to_ppl[j].append(i)
		return self.dfs(1, hats_to_ppl, dp, 0, (1 << ppl) - 1)

	def dfs(self, hat, hats_to_people, dp, cur_assignment, all_assignment):
		if cur_assignment == all_assignment:
			return 1
		if hat > 40:
			return 0
		if dp[hat][cur_assignment] != -1:
			return dp[hat][cur_assignment]
		res = self.dfs(hat + 1, hats_to_people, dp, cur_assignment, all_assignment)
		for i in hats_to_people[hat]:
			if cur_assignment >> i & 1 == 1:
				continue
			res += self.dfs(hat + 1, hats_to_people, dp, cur_assignment | 1 << i, all_assignment)
			res %= 10 ** 9 + 7
		dp[hat][cur_assignment] = res
		return res


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		h2p = collections.defaultdict(list)
		n = len(hats)
		MOD = 10 ** 9 + 7
		for (people, hat_list) in enumerate(hats):
			for h in hat_list:
				h2p[h].append(people)

		def dp(hat, mask):
			if (hat, mask) in memo:
				return memo[hat, mask]
			if mask == (1 << n) - 1:
				return 1
			if hat > 40:
				return 0
			ans = dp(hat + 1, mask)
			if hat in h2p:
				peoples = h2p[hat]
				for p in peoples:
					if mask & 1 << p == 0:
						ans += dp(hat + 1, mask | 1 << p)
			memo[hat, mask] = ans
			return ans
		memo = {}
		return dp(0, 0) % MOD


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		mod = 10 ** 9 + 7
		k = len(hats)
		persons = defaultdict(list)
		for (i, hs) in enumerate(hats):
			for h in hs:
				persons[h].append(i)
		dic = defaultdict(int)
		dic[0] = 1
		for (hat, ps) in persons.items():
			nex = dic.copy()
			for mask in dic:
				for p in ps:
					if mask >> p & 1 == 0:
						nex[mask | 1 << p] = (nex[mask | 1 << p] + dic[mask]) % mod
			dic = nex
		return dic[(1 << k) - 1]


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		MOD = int(1000000000.0) + 7
		n = len(hats)
		dp = [[0 for _ in range(1 << n)] for _ in range(41)]
		rev = [[] for _ in range(41)]
		for (i, h) in enumerate(hats):
			for e in h:
				rev[e].append(i)
		dp[0][0] = 1
		for i in range(40):
			r = rev[i + 1]
			for j in range(1 << n):
				dp[i + 1][j] += dp[i][j]
				dp[i + 1][j] %= MOD
				for k in r:
					if not j & 1 << k:
						dp[i + 1][j | 1 << k] += dp[i][j]
						dp[i + 1][j | 1 << k] %= MOD
		return dp[40][(1 << n) - 1]


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		hat2ppl = defaultdict(set)
		for (p, hats_i) in enumerate(hats):
			for h in hats_i:
				hat2ppl[h].add(p)
		if len(hats) > len(hat2ppl):
			return 0
		M = 10 ** 9 + 7

		@lru_cache(None)
		def dfs(h, mask):
			if h == 42:
				return 0
			if bin(mask).count('1') == len(hats):
				return 1
			ans = dfs(h + 1, mask)
			for p in hat2ppl[h]:
				x = 1 << p
				if mask & x == 0:
					mask |= x
					ans += dfs(h + 1, mask)
					mask ^= x
			return ans % M
		return dfs(1, 0) % M


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		N = len(hats)
		ppl = dict()
		for (i, hat) in enumerate(hats):
			for x in hat:
				ppl.setdefault(x, []).append(i)

		@lru_cache(None)
		def helper(h, mask):
			if mask == (1 << N) - 1:
				return 1
			if h == 40:
				return 0
			ans = helper(h + 1, mask)
			for p in ppl.get(h + 1, []):
				if mask & 1 << p:
					continue
				mask |= 1 << p
				ans += helper(h + 1, mask)
				mask ^= 1 << p
			return ans % 1000000007
		return helper(0, 0)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		dp = {}
		n_ppl = len(hats)
		hat_2_ppl = {}
		for i in range(n_ppl):
			for hat in hats[i]:
				hat_2_ppl[hat] = hat_2_ppl.get(hat, []) + [i]

		def dfs(hat, mask):
			if mask == (1 << n_ppl) - 1:
				return 1
			if hat > 40:
				return 0
			if hat in dp and mask in dp[hat]:
				return dp[hat][mask]
			res = dfs(hat + 1, mask)
			for ppl in hat_2_ppl.get(hat, []):
				if not mask & 1 << ppl:
					res += dfs(hat + 1, mask | 1 << ppl)
					res %= 1000000000 + 7
			dp[hat] = dp.get(hat, {})
			dp[hat][mask] = res
			return res
		return dfs(1, 0)


import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		LIMIT = 10 ** 9 + 7
		n = len(hats)
		final = 0
		dp = collections.defaultdict(lambda : -1)

		def dfs(row, path):
			if row >= n:
				return 0
			count = 0
			for hat in hats[row]:
				if 1 << hat & path:
					continue
				if row == n - 1:
					count += 1
				count += dfs(row + 1, path | 1 << hat)
			return count % LIMIT

		def dfs_dp(row, path):
			if row >= n:
				return 0
			if dp[row, path] != -1:
				return dp[row, path]
			count = 0
			for hat in hats[row]:
				if 1 << hat & path:
					continue
				if row == n - 1:
					count += 1
				count += dfs_dp(row + 1, path | 1 << hat)
			dp[row, path] = count % LIMIT
			return count % LIMIT
		hat_map = collections.defaultdict(set)
		for (person, j) in enumerate(hats):
			for hat in j:
				hat_map[hat].add(person)
		hats_list = list(hat_map.keys())
		hats_n = len(hats_list)
		final = pow(2, n) - 1

		def dfs_dp1(hat_index, path):
			if hat_index >= hats_n:
				if path == final:
					return 1
				return 0
			if dp[hat_index, path] != -1:
				return dp[hat_index, path]
			count = 0
			for person in hat_map[hats_list[hat_index]]:
				if 1 << person & path:
					continue
				count += dfs_dp1(hat_index + 1, path | 1 << person)
			count += dfs_dp1(hat_index + 1, path)
			dp[hat_index, path] = count % LIMIT
			return count % LIMIT
		return dfs_dp1(0, 0)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		hat2ppl = defaultdict(set)
		for (p, hats_i) in enumerate(hats):
			for h in hats_i:
				hat2ppl[h].add(p)
		M = 10 ** 9 + 7
		n = 1 << len(hats)
		dp = [0] * n
		dp[0] = 1
		for i in range(41, 0, -1):
			for j in range(n - 1, -1, -1):
				for p in hat2ppl[i]:
					if j & 1 << p:
						dp[j] = (dp[j] + dp[j ^ 1 << p]) % M
		return dp[-1]


from functools import lru_cache
p = 10 ** 9 + 7

class Solution:

	def numberWays(self, hats):
		max_hat_id = 0
		distinct_hats = set()
		for person_hats in hats:
			for i in range(len(person_hats)):
				person_hats[i] -= 1
				distinct_hats.add(person_hats[i])
		hat_id_mapping = dict()
		i = 0
		for hat in distinct_hats:
			hat_id_mapping[hat] = i
			i += 1
		persons = [[] for i in range(len(distinct_hats))]
		for p_id in range(len(hats)):
			for hat_id in hats[p_id]:
				persons[hat_id_mapping[hat_id]].append(p_id)
		dp = dict()
		for i in range(len(persons)):
			dp[i] = dict()
		allmask = (1 << len(hats)) - 1

		def get_number_of_ways(mask, hat_id):
			if mask == allmask:
				return 1
			if hat_id >= len(persons):
				return 0
			if (hat_id, mask) in dp:
				return dp[hat_id, mask]
			else:
				dp[hat_id, mask] = get_number_of_ways(mask, hat_id + 1)
			for i in persons[hat_id]:
				if (mask & 1 << i) >> i:
					continue
				temp_mask = mask | 1 << i
				val = get_number_of_ways(temp_mask, hat_id + 1)
				dp[hat_id, mask] += val
			return dp[hat_id, mask]
		ans = get_number_of_ways(0, 0)
		return ans % p


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		N = len(hats)
		for (i, h) in enumerate(hats):
			hats[i] = set(h)
		mod = 10 ** 9 + 7

		@lru_cache(None)
		def rec(cur, mask):
			if cur > 41:
				return 0
			if mask == 0:
				return 1
			ans = 0
			for i in range(N):
				if mask & 1 << i == 0:
					continue
				if cur not in hats[i]:
					continue
				ans += rec(cur + 1, mask ^ 1 << i)
			ans += rec(cur + 1, mask)
			return ans
		return rec(0, 2 ** N - 1) % mod


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		total = 1 << len(hats)
		(satisfy, bound) = ([0] * 41, 0)
		for (i, likes) in enumerate(hats):
			for hat in likes:
				satisfy[hat] |= 1 << i
				bound = max(bound, hat)
		MOD = 10 ** 9 + 7
		DP = [1] + [0] * (total - 1)
		for hat in range(1, bound + 1):
			new_DP = [0] * total
			for state in range(total):
				new_DP[state] = DP[state]
				(can_satisfy, mask) = (satisfy[hat] & state, 1)
				while can_satisfy != 0:
					if can_satisfy & 1:
						new_DP[state] += DP[state ^ mask]
					can_satisfy >>= 1
					mask <<= 1
				new_DP[state] %= MOD
			DP = new_DP
		return DP[total - 1]


class Solution:

	def _to_hat_to_people(self, person_to_hats):
		(min_hat, max_hat) = (None, None)
		for hats in person_to_hats:
			for hat in hats:
				if min_hat is None or hat < min_hat:
					min_hat = hat
				if max_hat is None or hat > max_hat:
					max_hat = hat
		number_of_hats = max_hat - min_hat + 1
		hats_to_people = [[] for _ in range(number_of_hats)]
		for person in range(len(person_to_hats)):
			for hat in person_to_hats[person]:
				hats_to_people[hat - min_hat].append(person)
		return hats_to_people

	def numberWays(self, person_to_hats):
		hat_to_people = self._to_hat_to_people(person_to_hats)

		def _number_of_ways(person_to_hat_presence, hat, cache):
			if all(person_to_hat_presence):
				return 1
			if hat >= len(hat_to_people):
				return 0
			key = (hat, tuple(person_to_hat_presence))
			if key in cache:
				return cache[key]
			else:
				sum = 0
				for person in hat_to_people[hat]:
					if not person_to_hat_presence[person]:
						updated_person_to_hat_presence = person_to_hat_presence.copy()
						updated_person_to_hat_presence[person] = True
						sum += _number_of_ways(updated_person_to_hat_presence, hat + 1, cache)
				sum += _number_of_ways(person_to_hat_presence, hat + 1, cache)
				cache[key] = sum % (10 ** 9 + 7)
				return cache[key]
		return _number_of_ways([False] * len(person_to_hats), 0, {})


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		max_hat = max([item for hat in hats for item in hat])
		n = len(hats)
		dp = [[0 for _ in range(2 ** n)] for _ in range(max_hat + 1)]
		for i in range(max_hat + 1):
			dp[i][0] = 1
		hat_bitmaps = []
		for i in range(n):
			bitmap = 0
			for j in hats[i]:
				bitmap |= 1 << j
			hat_bitmaps.append(bitmap)
		for i in range(1, max_hat + 1):
			for j in range(2 ** n):
				acc = 0
				for k in range(n):
					cur_bit = 1 << k
					if j & cur_bit != 0 and 1 << i & hat_bitmaps[k] != 0:
						acc += dp[i - 1][j - cur_bit]
				dp[i][j] = (dp[i - 1][j] + acc) % 1000000007
		return dp[max_hat][2 ** n - 1]


from functools import lru_cache
from operator import iconcat
from functools import reduce

class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		MOD = 10 ** 9 + 7
		hat_ids = list(set(reduce(iconcat, hats, [])))
		n = len(hats)
		m = len(hat_ids)
		k = (1 << n) - 1

		@lru_cache(None)
		def dp(i, used):
			if i == m:
				return 1 if used == k else 0
			total = dp(i + 1, used)
			for p in range(n):
				if used & 1 << p == 0 and hat_ids[i] in hats[p]:
					total += dp(i + 1, used | 1 << p)
			return total % MOD
		return dp(0, 0)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		self.visited = 0
		hm = {}
		for (n, i) in enumerate(hats):
			for j in i:
				if j not in hm:
					hm[j] = [n]
				else:
					hm[j].append(n)
		keys = list(hm.keys())
		self.saved = {}

		def helper(index):
			if (index, self.visited) in self.saved:
				return self.saved[index, self.visited]
			if self.visited == (1 << len(hats)) - 1:
				return 1
			if index == len(keys):
				return 0
			count = 0
			for i in hm[keys[index]]:
				if not self.visited & 1 << i:
					self.visited |= 1 << i
					count += helper(index + 1)
					self.visited ^= 1 << i
			self.saved[index, self.visited] = count + helper(index + 1)
			return self.saved[index, self.visited]
		return helper(0) % (10 ** 9 + 7)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		N = len(hats)

		@lru_cache(None)
		def helper(mask, i):
			if i == 41:
				if mask == 0:
					return 1
				else:
					return 0
			elif mask == 0:
				return 1
			else:
				total = 0
				for pers in range(N):
					if mask & 1 << pers and i in hats[pers]:
						total += helper(mask ^ 1 << pers, i + 1)
				total += helper(mask, i + 1)
				return total
		return helper(2 ** N - 1, 1) % (10 ** 9 + 7)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		tot = len(hats)
		h = [[False] * tot for i in range(41)]
		for i in range(len(hats)):
			for j in range(len(hats[i])):
				h[hats[i][j]][i] = True
		f = [[0] * (1 << tot) for i in range(41)]
		f[0][0] = 1
		mod = 10 ** 9 + 7
		for i in range(41):
			for j in range(1 << tot):
				f[i][j] = (f[i][j] + f[i - 1][j]) % mod
				for k in range(tot):
					if j & 1 << k != 0 and h[i][k]:
						f[i][j] = (f[i][j] + f[i - 1][j ^ 1 << k]) % mod
		return f[40][(1 << tot) - 1]


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		numPeople = len(hats)
		hatDesired = defaultdict(set)
		MAX_HATS = 0
		BIG_NUMBER = 10 ** 9 + 7
		for (index, hatPreferences) in enumerate(hats):
			for hat in hatPreferences:
				hatDesired[hat].add(index)
				MAX_HATS = max(MAX_HATS, hat)
		numberWays = defaultdict(int)

		def computeWays(assigned, currentHat):
			if (assigned, currentHat) in numberWays:
				return numberWays[assigned, currentHat]
			else:
				if currentHat == MAX_HATS + 1:
					if sum(assigned) != numPeople:
						answer = 0
					else:
						answer = 1
				else:
					answer = 0
					answer += computeWays(assigned, currentHat + 1)
					answer %= BIG_NUMBER
					for (index, num) in enumerate(assigned):
						if num == 0 and index in hatDesired[currentHat]:
							nextList = list(assigned)
							nextList[index] = 1
							nextTuple = tuple(nextList)
							answer += computeWays(nextTuple, currentHat + 1)
							answer %= BIG_NUMBER
				numberWays[assigned, currentHat] = answer
				return answer
		return computeWays(tuple([0] * numPeople), 1)


class Solution:

	def numberWays(self, hats: List[List[int]]) -> int:
		self.hat_to_man = collections.defaultdict(set)
		for (i, lt) in enumerate(hats):
			for hat in lt:
				self.hat_to_man[hat].add(i)
		self.hat_nums = sorted(self.hat_to_man)
		self.hat_cnt = len(self.hat_nums)
		self.man_cnt = len(hats)
		self.mem = dict()
		return self.dfs(0, set())

	def dfs(self, idx, used):
		if idx >= self.hat_cnt:
			return 0
		key = (idx, frozenset(used))
		if key in self.mem:
			return self.mem[key]
		hat = self.hat_nums[idx]
		res = 0
		for x in self.hat_to_man[hat] - used:
			used.add(x)
			if len(used) == self.man_cnt:
				res += 1
				used.remove(x)
				continue
			res += self.dfs(idx + 1, used)
			used.remove(x)
		res += self.dfs(idx + 1, used)
		self.mem[key] = res
		return res % (10 ** 9 + 7)