<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:
        # 40 kinds of hats
        # hats[i] is the list of hats each person can wear
        # how many ways can the people wear different hats?

        # fun problem, also seems hard though

        BIG = 10**9 + 7 

        # ideas:
        #   top-down DFS: would work, but mask to track selected hats at i~20 would have 40 choose 20 combos. too expensive
        #   DP: need a subproblem
        #   graph: interesting idea with length=20 path count, but also not clear how to avoid "repeat visits" efficiently
        #      >> can't assign the same hat twice
        #      >> can't assign the same person two+ hats

        # "hat space:"
        #    >> to avoid assigning the same hat twice: edges among hats ascending
        #       those edges would be the higher hats and the people that would wear them

        # WAIT: n is at most 10!!!
        # 40 choose 10 is...
        # 40*...*31/10!
        # that's almost a billion though
        
        # idk, just try something
        # n = len(hats)
        # for hs in hats: hs.sort()
        # hats.sort(key=lambda hs: (len(hs), hs)) # by length first to reduce complexity
        # ALL = (1 << 41) - 1

        # @cache
        # def ways(i: int, rem: int) -> int:
        #     if i == n: return 1

        #     ans = 0
        #     for h in hats[i]:
        #         b = 1 << h
        #         if rem & b:
        #             ans += ways(i+1, rem ^ b)

        #     return ans

        # return ways(0, ALL)

        # as expected: TLE at a big problem where 7 people have most of 1..25 as options,
        # and an 8th person only has about 2 options

        # I GIVE UP. Interesting problem, but I clearly lack a technique or insight to solve this.

        # Wait: 5 more minutes

        # that was 10 minutes... another 10 I swear!!

        # okay now I really give up

        # glanced at a solution, poorly explained but the idea is this:
        #   instead of dfs(i, hatMask), do dfs(h, peopleMask)

        # i, hatMask: iterate over the <= 40 hats, call dfs(i+1, hatMask ^ picked)
        #      so it's O(1) * numDfsStates
        #      states for person i, 0 indexed: we've chosen i of the 40 hats. 40 choose i states.
        #      so it's 40 choose 0 + ... + 40 choose 9 for dfs(0, mask), dfs(1, mask), etc. (<= 9 people)
        # this is worst case 2^n, although a lot less (only about 0.03% of that)

        # h, personMask: iterate over the <= 10 people, call dfs(h+1, r-1, personMask ^ assigned)
        #          or don't assign h: call dfs(h+1, r, personMask)

        # for hat h:
        #     if we assigned zero hats thus far: r==n, 10 choose 0
        #                     one hat  thus far: r==n-1, 10 choose 1
        #                    ...
        #          total: sum of 10 choose k => 2^10 ~ 1000
        #  this holds for all hats h: 40*1000
        #  and we need to iterate over <= 10 people who can wear hat h: another 10x: 400*1000

        H = max(max(hs) for hs in hats) + 1
        P = len(hats)

        people = [[] for _ in range(H)] # people[h] are the people that can wear h
        for p, hs in enumerate(hats):
            for h in hs:
                people[h].append(p)


        ALL = (1 << (P+1)) - 1 # P+1 b/c they're 1-indexed in `hats`

        @cache
        def ways(h: int, r: int, rem: int) -> int:
            """Returns ways to assign r of hats h..H-1 to hatless people, bit-encoded as rem"""

            if r > H-h: return 0 # can't assign more than H-h hats
            if r == 0: return 1

            ans = ways(h+1, r, rem) # ways that don't involve assigning h
            for p in people[h]:
                b = 1 << p
                if rem & b:
                    ans += ways(h+1, r-1, rem ^ b) # assign h to p (encoded as b) and continue

            return ans % BIG

        return ways(h=1, r=P, rem=ALL)
37100