1const MOD = 10**9 + 7;
2
3function numberOfWays(hats) {
4    const n = hats.length;
5    const allMask = (1 << n) - 1;
6    const dp = new Map();
7    const hatToPeople = Array.from({ length: 41 }, () => []);
8
9    hats.forEach((hatList, person) => {
10        hatList.forEach(hat => {
11            hatToPeople[hat].push(person);
12        });
13    });
14
15    function ways(hat, mask) {
16        if (mask === allMask) return 1;
17        if (hat > 40) return 0;
18        const key = `${hat},${mask}`;
19        if (dp.has(key)) return dp.get(key);
20        let ans = ways(hat + 1, mask);
21        hatToPeople[hat].forEach(person => {
22            if ((mask & (1 << person)) === 0) {
23                ans += ways(hat + 1, mask | (1 << person));
24                ans %= MOD;
25            }
26        });
27        dp.set(key, ans);
28        return ans;
29    }
30
31    return ways(1, 0);
32}

1#include <vector>
2#include <unordered_map>
3
4using namespace std;
5#define MOD 1000000007

int numberOfWays(vector<vector<int>>& hats) {
    int n = hats.size();
    vector<vector<int>> people_with_hat(41);
    for (int i = 0; i < n; ++i) {
        for (int hat : hats[i]) {
            people_with_hat[hat].push_back(i);
        }
    }
    unordered_map<int, int> dp;
    return dfs(0, 0, people_with_hat, dp, n);
}

int dfs(int hat, int mask, vector<vector<int>>& people_with_hat, unordered_map<int, int>& dp, int n) {
    if (mask == (1 << n) - 1) return 1;
    if (hat > 40) return 0;
    if (dp.count((hat << 10) | mask)) return dp[(hat << 10) | mask];
    int ans = dfs(hat + 1, mask, people_with_hat, dp, n);
    for (int person : people_with_hat[hat]) {
        if (!(mask & (1 << person))) {
            ans = (ans + dfs(hat + 1, mask | (1 << person), people_with_hat, dp, n)) % MOD;
        }
    }
    dp[(hat << 10) | mask] = ans;
    return ans;
}