1MOD = 10**9 + 7
2
3def number_ways(hats):
4    n = len(hats)
5    all_mask = (1 << n) - 1
6    dp = {}
7    hat_to_people = [[] for _ in range(41)]
8    for person, hat_list in enumerate(hats):
9        for hat in hat_list:
10            hat_to_people[hat].append(person)
11    
12    def ways(hat, mask):
13        if mask == all_mask:
14            return 1
15        if hat > 40:
16            return 0
17        if (hat, mask) in dp:
18            return dp[(hat, mask)]
19        ans = ways(hat + 1, mask)
20        for person in hat_to_people[hat]:
21            if mask & (1 << person) == 0:
22                ans += ways(hat + 1, mask | (1 << person))
23                ans %= MOD
24        dp[(hat, mask)] = ans
25        return ans
26    
27    return ways(1,0)

1#include <vector>
2#include <unordered_map>
3
4using namespace std;
5#define MOD 1000000007
6
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;
}