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: interview

Starter code:

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

Solutions:
class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        # assign hat to people
        n = len(hats)
        dic = collections.defaultdict(list)
        for i,hat in enumerate(hats):
            for h in hat:
                dic[h].append(i)
        
        # mask for people: ways
        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(1e9) + 7
        n = len(hats)
        # dp = [[0 for _ in range(1 << n)] for _ in range(41)]
        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:
        MOD = int(1e9) + 7
        n = len(hats)
        # dp = [[0 for _ in range(1 << n)] for _ in range(41)]
        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 = {}
            for j in d:
                nx[j] = (nx.get(j, 0) + d[j]) % MOD
                for k in r:
                    if not (j & (1 << k)):
                        nx[j | (1 << k)] = (nx.get(j | (1 << k), 0) + d[j]) % MOD
            d = nx
        return d.get((1 << n) - 1, 0)

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        ## https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/discuss/608778/Java-Top-down-DP-%2B-Bitmask-Clean-code
        ## hat: current hat; assignedPeople: bitmask for n people (0: this person has not been assigned a hat, 1 otherwise)
        
        def helper(hat, assignedPeople):
            if assignedPeople == target_state:
                return 1
                
            if hat>40: ## no remaining hat 
                return 0
            
            if dp[hat][assignedPeople] is not None:
                return dp[hat][assignedPeople]
            
            res = 0 
            ## case 1: do not use current hat
            res += helper(hat+1, assignedPeople)
            
            ## case 2: use current hat
            ## check every possible person that is allowed to wear the current hat
            for person in hat2person[hat]:
                ## if person has a hat already
                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
        ## h2p[i] indicates the list of people who can wear i_th hat
        hat2person = [[] for _ in range(41)] 
        for i in range(n):
            for hat in hats[i]:
                hat2person[hat].append(i)
        # print(hat2person)
        target_state = (1<<n)-1 ## all people have weared a hat
        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)
        
        '''
        def dp(h, mask):
            if (h, mask) in memo:
                return memo[(h,mask)]
            
            if mask == (1 << n) - 1:
                return 1
        
            if h > 40:
                return 0
            
            ans = dp(h+1, mask)
            
            if h in h2p:
                peoples = h2p[h]
                
                for p in peoples:
                    if mask & (1 << p) == 0:
                        mask |= (1 << p)
                        ans += dp(h+1, mask)
                        mask ^= (1 << p)
            
            memo[(h,mask)] = ans
            
            return ans
        
        memo = {}
        
        return dp(0, 0) % mod
        '''
        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:
#         const = 10**9+7
#         cache = {}
#         matr = [[False]*len(hats) for i in range(40)]
#         maxx = -1
#         used_h = set()
#         for j in range(len(hats)):
#             for i in hats[j]:
#                 matr[i-1][j] = True
#                 maxx = max(i-1, maxx)
#                 used_h.add(i-1)
#         def s(mask_p, h, n):
#             if h < 0 or n > h+1:
#                 return 0
#             c = str(h)+mask_p
#             if c in cache:
#                 return cache[c]
#             res = s(mask_p, h-1, n)
#             if h in used_h:
#                 for p in range(len(matr[h])):
#                     if mask_p[p] == \"1\" and matr[h][p]:
#                         if n > 1:
#                             res += s(mask_p[:p] + \"0\" + mask_p[p+1:], h-1, n-1)
#                         else:
#                             res += 1
#             cache[c] = res%const
#             return res%const
#         mask_p = \"1\"*len(hats)
#         return s(mask_p, maxx, len(hats))%const
    
    
# 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] = matr[i-1] ^ (1 << 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 = bin(mask_p & matr[h])
#                 for p in range(2, len(b)):
#                     if b[p] == \"1\":
#                         res += s(mask_p ^ (1 << (len(b)-p-1)), n-1, h-1, c_h, cache)
#             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: List[List[int]]) -> int:
        h2p = defaultdict(list)
        for i, hat in enumerate(hats):
            for h in hat:
                h2p[h].append(i)
        n = len(hats)
 
        # bottom up
        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:
        h2p = defaultdict(list)
        for i, hat in enumerate(hats):
            for h in hat:
                h2p[h].append(i)
        n = len(hats)
 
        # bottom up
        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]

# Time: O(40 * 2^n * n), where n is the number of people, n <= 10
# Explain: There are total hat*assignedPeople = 40*2^n states in dfs(..hat, assignedPeople...) function, each state needs a loop up to n times (int p : h2p[hat]) to calculate the result.
# Space: O(40 * 2^n)

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)
                
        # Remove entries for unwanted hats
        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):
            # Mask signifies person state
            if i == num_hats:
                if bin(mask).count('1') == num_ppl:
                    return 1
                else:
                    return 0
                        
            # Not using current hat             
            res = dp(i+1, mask)
            
            for person in hat_to_ppl[i]:
                # Person is not wearing a hat already                 
                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():
                    # print(f'{bin(state)}/{state}: {cnt}, {dp}: {dp[state]}')
                    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:
        # mask = (1<<10)-1 #-> person i is wearing a hat already
        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:
        # 10 ppl, 40 hats.
        # each person, choose a hat which is not taken.
        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:
                    # this person can wear.
                    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: 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 in range(1<<n):
                    cnt = dp[state] if state in dp else 0
                    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
        return dp[(1<<n)-1] % (10**9+7)

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:
        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
        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:
        htop = [[] for i in range(41)] # htop: hat to people list
        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]) # filter out hats no one wants
        
        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) # not using the current hat
            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:        
#         hat2ppl = defaultdict(set)        
#         for i, hats_i in enumerate(hats):
#             for h in hats_i:
#                 hat2ppl[h].add(i)
#         if len(hats) > len(hat2ppl): return 0        
#         @lru_cache(None)
#         def dfs(h, mask):
#             print(h, mask)
#             if h == 40: return            
#             if mask == (1 << len(hats)) - 1: return 1
#             dfs(h+1, mask)
#             ans = 0
#             for p in hat2ppl.get(h, set()):
#                 x = 1 << p
#                 if mask & x == 0:
#                     mask |= x
#                     ans += dfs(h+1, mask)
#                     mask ^= x
#             return ans % (10**9 + 7)        
#         return dfs(0, 0) 


# class Solution:
#     def numberWays(self, hats: List[List[int]]) -> int:
#         const = 10**9+7
#         cache = {}
#         matr = [[False]*len(hats) for i in range(40)]
#         maxx = -1
#         used_h = set()
#         for j in range(len(hats)):
#             for i in hats[j]:
#                 matr[i-1][j] = True
#                 maxx = max(i-1, maxx)
#                 used_h.add(i-1)
#         def s(mask_p, h, n):
#             if h < 0 or n > h+1:
#                 return 0
#             c = str(h)+mask_p
#             if c in cache:
#                 return cache[c]
#             res = s(mask_p, h-1, n)
#             if h in used_h:
#                 for p in range(len(matr[h])):
#                     if mask_p[p] == \"1\" and matr[h][p]:
#                         if n > 1:
#                             res += s(mask_p[:p] + \"0\" + mask_p[p+1:], h-1, n-1)
#                         else:
#                             res += 1
#             cache[c] = res%const
#             return res%const
#         mask_p = \"1\"*len(hats)
#         return s(mask_p, maxx, len(hats))%const
    
    
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
                # b = bin(mask_p & matr[h])
                # for p in range(2, len(b)):
                #     if b[p] == \"1\":
                #         res += s(mask_p ^ (1 << (len(b)-p-1)), n-1, h-1, c_h, cache)
            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))
                        # mask|=(1<<p)
                        # ans += dp(h+1,mask)
                        # mask ^= (1<<p)
            memo[(hat,mask)] = ans
            return ans
        
        memo ={}
        return dp(0,0)%MOD

        
        
        
        
        
        
#         h2p = collections.defaultdict(list)
#         n = len(hats) # number of people
        
#         for people,hat_list in enumerate(hats):
#             for h in hat_list:
#                 h2p[h].append(people)
        
#         def dp(hat,mask): # hat index and people bit mask,  since n<=10,so use people as bitmask, otherwise if uses hat will TLE
#             if (hat,mask) in memo:return memo[(hat,mask)]
            
#             if mask == (1<<n)-1: # base case
#                 return 1
#             if h >40:return 0
#             # not use current hat
#             ans = dp(hat+1,mask) 
#             # use current hat
#             if hat in h2p:
#                 peoples = h2p[hat]
#                 for p in peoples:
#                     if mask & (1<<p) == 0: # means this people has not assigned a hat yet
#                         mask |= (1<<p)
#                         ans += dp(hat+1,mask)
#                         mask ^= (1<<p)
#                         # ans += dp(hat+1,mask|(1<<p))
#             memo[(hat,mask)] = ans
#             return ans
#         memo = {}
#         return dp(0,0)


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(1e9) + 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:
#         htop = [[] for i in range(41)] # htop: hat to people list
#         for p, prefer_hats in enumerate(hats):
#             for h in prefer_hats:
#                 htop[h].append(p)
#         htop = list(filter(lambda h: h, htop)) # filter out hats no one wants
        
#         num_hats, num_people = len(htop), len(hats)
#         if num_hats < num_people:
#             return 0
#         print(htop)
#         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) # not using the current hat
#             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:        
        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 mask covered all the people set bits == people
            if h == 40: return 0 ## if all hats are being used
            
            ans = helper(h+1, mask)
            
            for p in ppl.get(h+1, []): ## loop through all the people preferring the hat
                if mask & (1 << p):  ## if taken already continue
                    continue
                    
                mask |= 1 << p  ## set bit
                
                ans += helper(h+1, mask)
                
                mask ^= 1 << p  ## reset bit
                
            return ans% 1_000_000_007
        
        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)

# class Solution:
#     def numberWays(self, hats: List[List[int]]) -> int:
#         const = 10**9+7
#         cache = {}
#         matr = [[False]*len(hats) for i in range(40)]
#         maxx = -1
#         used_h = set()
#         for j in range(len(hats)):
#             for i in hats[j]:
#                 matr[i-1][j] = True
#                 maxx = max(i-1, maxx)
#                 used_h.add(i-1)
#         def s(mask_p, h, n):
#             if h < 0 or n > h+1:
#                 return 0
#             c = str(h)+mask_p
#             if c in cache:
#                 return cache[c]
#             res = s(mask_p, h-1, n)
#             if h in used_h:
#                 for p in range(len(matr[h])):
#                     if mask_p[p] == \"1\" and matr[h][p]:
#                         if n > 1:
#                             res += s(mask_p[:p] + \"0\" + mask_p[p+1:], h-1, n-1)
#                         else:
#                             res += 1
#             cache[c] = res%const
#             return res%const
#         mask_p = \"1\"*len(hats)
#         return s(mask_p, maxx, len(hats))%const
    
    
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 % 2 == 0:
                        b /= 2
                    else:
                        b -= 1
                        b /= 2
                        res += s(mask_p - 2**(i), n-1, h-1, c_h, cache)
                    i += 1
                # b = bin(mask_p & matr[h])[2:]
                # for p in range(len(b)):
                #     if b[p] == \"1\":
                #         res += s(mask_p - 2**(len(b)-p-1), n-1, h-1, c_h, cache)
            res += s(mask_p, n, h-1, c_h, cache)
            cache[mask_p][h] = res%const
            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)])

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

'''
每个人都不同喜欢的帽子，求分配方案数量

hats = [[3,4],[4,5],[5]]
1

dfs: 
\t   [3,4]
\t     | 
\t   [4,5]

显然：
\tdp[start_person + 1][chose_hats + new_in] += dp[start_person][chose_hats + new_in]
\t   
n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40


'''


class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        LIMIT = 10**9 + 7

        n = len(hats)
        final = 0
        dp = collections.defaultdict(lambda: -1)

        # 普通dfs
        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

        #  复杂度 O(2^40 * 10).
        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 

        # 与其person映射hat, 不如hat映射person
        # 复杂度 O(2^10 * 40).

        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 get_number_of_ways(self, hats, mask, p_id): #p_id = person_id
#         if p_id>=len(hats):
#             return 1
        
#         if dp[p_id].get(mask, None):
#             return dp[p_id][mask]
#         else:
#             dp[p_id][mask] = 0
        
#         for i in hats[p_id]:
#             if (mask & (1<<i))>>i :
#                 continue
#             temp_mask = mask | (1<<i)
#             val = self.get_number_of_ways(hats, temp_mask, p_id+1)
#             if val == -1:
#                 continue
            
#             dp[p_id][mask] += val
        
#         return dp[p_id][mask]

        
    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): #p_id = person_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
        
        
        
        
        
        # @lru_cache(None)
#         def get_number_of_ways( mask, hat_id, allmask): #p_id = person_id
#             if mask == allmask :
#                 return 1
#             if hat_id>=len(persons):
#                 return 0
            
#             if dp[hat_id].get(mask, None):
#                 return dp[hat_id][mask]
#             else:
#                 dp[hat_id][mask] = get_number_of_ways( mask, hat_id+1, allmask)
#             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, allmask)
                
#                 dp[hat_id][mask] += val
            
#             return dp[hat_id][mask]
            
        
        
#         return get_number_of_ways( 0, 0, allmask) % 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:
                # O(40 * 2 ^ 10 * 10)
        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):
                # do not use current hat
                new_DP[state] = DP[state]
                # use current hat
                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 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)
            while ans >= mod:
                ans -= mod
            return ans
        
        return rec(0, (2**N)-1)

class Solution:
    # def numberWays(self, hats: List[List[int]]) -> int:
        # const = 10**9+7
        # cache = {}
        # matr = [[False]*len(hats) for i in range(40)]
        # maxx = -1
        # used_h = [False]*40
        # for j in range(len(hats)):
        #     for i in hats[j]:
        #         matr[i-1][j] = True
        #         maxx = max(i-1, maxx)
        #         used_h[i-1] = True
        # def s(mask_p, h, n):
        #     if n > h+1 or h < 0:
        #         return 0
        #     c = str(h)+mask_p
        #     if c in cache:
        #         return cache[c]
        #     res = s(mask_p, h-1, n)
        #     if used_h[h]:
        #         for p in range(len(matr[h])):
        #             if mask_p[p] == \"1\" and matr[h][p]:
        #                 if n > 1:
        #                     res += s(mask_p[:p] + \"0\" + mask_p[p+1:], h-1, n-1)
        #                 else:
        #                     res += 1
        #     cache[c] = res%const
        #     return cache[c]
        # mask_p = \"1\"*len(hats)
        # return s(mask_p, maxx, len(hats))%const


        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

        
        
        
        
        
        
        
        
        
        
        

    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:
        # const = 10**9+7
        # cache = {}
        # matr = [[False]*len(hats) for i in range(40)]
        # maxx = -1
        # used_h = [False]*40
        # for j in range(len(hats)):
        #     for i in hats[j]:
        #         matr[i-1][j] = True
        #         maxx = max(i-1, maxx)
        #         used_h[i-1] = True
        # def s(mask_p, h, n):
        #     if n > h+1 or h < 0:
        #         return 0
        #     c = str(h)+mask_p
        #     if c in cache:
        #         return cache[c]
        #     res = s(mask_p, h-1, n)
        #     if used_h[h]:
        #         for p in range(len(matr[h])):
        #             if mask_p[p] == \"1\" and matr[h][p]:
        #                 if n > 1:
        #                     res += s(mask_p[:p] + \"0\" + mask_p[p+1:], h-1, n-1)
        #                 else:
        #                     res += 1
        #     cache[c] = res%const
        #     return cache[c]
        # mask_p = \"1\"*len(hats)
        # return s(mask_p, maxx, len(hats))%const


        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

        
        
        
        
        
        
        
        
        
        
        

    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 _number_of_ways(self, hat_to_people, 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 += self._number_of_ways(hat_to_people, updated_person_to_hat_presence, hat + 1, cache)
            sum += self._number_of_ways(hat_to_people, person_to_hat_presence, hat + 1, cache)
            cache[key] = sum%(10**9+7)
            return cache[key]

    def numberWays(self, person_to_hats):
        hat_to_people = self._to_hat_to_people(person_to_hats)
        return self._number_of_ways(hat_to_people, [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]
    


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, n = 10**9 + 7, 1 << len(hats)
        dp = [0]*n
        dp[0] = 1
        for h in hat2ppl:
            for j in range(n-1, -1, -1):
                for p in hat2ppl[h]:       
                    if j & (1 << p):                        
                        dp[j] = (dp[j] + dp[j ^ (1 << p)]) % M                        
        return dp[-1]                            

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 = tuple(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

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):
            # print(mask,i)
            if i == 41:
                if mask == 0:
                    return 1
                else:
                    return 0
            elif mask == 0:
                return 1
            else:
                total = 0
                # for pref in hats[i]:
                #     if mask & (1 << pref):
                #         total += helper(mask ^ (1 << pref), i+1)
                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]


import functools as ft
class Solution:
    # def numberWays(self, hats: List[List[int]]) -> int:
    #     cache = {}
    #     l = len(hats)
    #     def f(allowed, i):
    #         if i == l:
    #             return 1
    #         key = (tuple(allowed), i)
    #         if key in cache:
    #             return cache[key]
    #         c = 0
    #         for hat in hats[i]:
    #             if allowed[hat]:
    #                 allowed[hat] = False
    #                 c += f(allowed, i+1)
    #                 allowed[hat] = True
    #         cache[key] = c
    #         return c
    #     allowed = [True]*40
    #     return f(allowed, 0)
    def numberWays(self, hats: List[List[int]]) -> int:
        const = 10**9+7
        cache = {}
        matr = [[False]*10 for i in range(40)]
        for j in range(len(hats)):
            for i in hats[j]:
                matr[i-1][j] = True
        def s(mask_p, h, n):
            if n == 0:
                return 1
            if h < 0:
                return 0
            c = tuple(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, 39, len(hats))%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(hats_to_ppl,dp,1,0,(1<<ppl)-1)
    def dfs(self,hats_to_ppl,dp,hat,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(hats_to_ppl,dp,hat+1,cur_assignment,all_assignment)

        for ppl in hats_to_ppl[hat]:
            if ((cur_assignment >> ppl) & 1) == 1:
                continue
            res += self.dfs(hats_to_ppl,dp,hat+1, cur_assignment | (1 << ppl),all_assignment)
            res %= 10 ** 9 + 7
        dp[hat][cur_assignment] = res
        return res
        


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:
                return 0
            c = tuple(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:        
        hat2ppl = defaultdict(set)        
        for p, hats_i in enumerate(hats):
            for h in hats_i: hat2ppl[h].add(p)

        M, n = 10**9 + 7, 1 << len(hats)
        dp = [0] * n
        dp[0] = 1
        for h in hat2ppl:
            for j in range(n-1, -1, -1):
                for p in hat2ppl[h]:       
                    if j & (1 << p):                        
                        dp[j] = (dp[j] + dp[j ^ (1 << p)]) % M                        
        return dp[-1]                            

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:
        ownhat={}
        n=len(hats)
        maxhat=-1
        for i in range(n):
            hat=hats[i]
            for h in hat:
                maxhat=max(h,maxhat)
                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)]
        @lru_cache(None)
        def dfs(ind,peoplemask):
            if(peoplemask==pow(2,n)-1):
                return 1
            if(ind>maxhat):
                return 0
            count=0
            # if(dp[ind][peoplemask]!=-1):
            #     return dp[ind][peoplemask]
            count=dfs(ind+1,peoplemask)
            if(ind in ownhat):
                for people in ownhat[ind]:
                    if(peoplemask & (pow(2,people))==0):
                        count=(count+dfs(ind+1,peoplemask | pow(2,people))) % (pow(10,9)+7)
            # dp[ind][peoplemask]=count
            return count
        return dfs(1,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
        
        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 i in hats[k]:
                        acc += dp[i-1][j - cur_bit]
                dp[i][j] = (dp[i-1][j] + acc) % 1000000007
    
        return dp[max_hat][2 ** n - 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)##don't assign currentHat to anyone.
                    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)##be careful about arguments you provide


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)