<p>There are <code>n</code> people and <code>40</code> types of hats labeled from <code>1</code> to <code>40</code>.</p>

<p>Given a 2D integer array <code>hats</code>, where <code>hats[i]</code> is a list of all hats preferred by the <code>i<sup>th</sup></code> person.</p>

<p>Return <em>the number of ways that the <code>n</code> people wear different hats to each other</em>.</p>

<p>Since the answer may be too large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> hats = [[3,4],[4,5],[5]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> hats = [[3,5,1],[3,5]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 ways to choose hats:
(3,5), (5,3), (1,3) and (1,5)
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == hats.length</code></li>
	<li><code>1 &lt;= n &lt;= 10</code></li>
	<li><code>1 &lt;= hats[i].length &lt;= 40</code></li>
	<li><code>1 &lt;= hats[i][j] &lt;= 40</code></li>
	<li><code>hats[i]</code> contains a list of <strong>unique</strong> integers.</li>
</ul>

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        
        mod = 10 ** 9 + 7
        n = len(hats)
        
        # bitmask to store which people have been assigned a hat
        taken = 0
        
        # hashmap to store which people can wear a particular hat
        # key -> hat, value -> List of people
        hatToPerson = {}
        
        # hat numbers of hats present in the hats list
        hatsavailable = set()
        
        for i in range(len(hats)):
            for hat in hats[i]:
                if hat not in hatToPerson:
                    hatToPerson[hat] = set()
                    hatsavailable.add(hat)
                hatToPerson[hat].add(i)
                
        # list to store all the available hats from available hats set
        finalhats = []
        for hat in hatsavailable:
            finalhats.append(hat)
            
        # hashmap to memoize
        memo = {}
        def dp(idx, taken, memo):
            # if all person are assigned a hat
            if taken == (1 << n) - 1:
                return 1
            
            # if we reached end of list and no answer found
            if idx == len(finalhats):
                return 0
            
            # if we already processed this state
            if (idx, taken) in memo:
                return memo[(idx, taken)]
            
            # if we are not picking the current hat
            notPick = dp(idx + 1, taken, memo) % mod
            
            pick = 0
            # trying to assign every person who can wear that hat
            for person in hatToPerson[finalhats[idx]]:
                
                # if that person is not assigned a hat already
                if (1 << person) & taken == 0:
                    taken += (1 << person)
                    pick = (pick + dp(idx + 1, taken, memo)) % mod
                    taken -= (1 << person)
            # caching        
            memo[(idx, taken)] = (notPick + pick) % mod
            return (notPick + pick) % mod
        
        return dp(0, taken, memo)
22700