I knew it was some kind of DP but spent way too long thinking about it person-by-person before realizing you should iterate over hats instead, since there are only 40 hats but up to 10 people.
Model the problem as counting perfect matchings in a bipartite graph where people are on one side and hats on the other, with edges representing allowed assignments. Use DP over subsets of people (since n ≤ 10) to count assignments, iterating over hats and updating the set of assigned people. Apply modulo 10^9+7 to handle large numbers.
Pro tip: Mention that the small n (≤10) makes bitmask DP feasible, and that the 40 hat types are handled by iterating over hats and updating the DP state; this avoids exponential blowup in hats. Also, clarify that each hat can be used at most once, so the DP state must track which people have been assigned.
Restate the problem: assign exactly one hat to each person from their allowed set, with no two people sharing a hat. Note n ≤ 10 and 40 hat types, so a bitmask DP over people is efficient.
Let dp[mask] be the number of ways to assign hats to the subset of people represented by mask. Initialize dp[0] = 1. For each hat, update dp by considering assigning it to any unassigned person who allows it, adding dp[mask] to dp[mask | (1<<i)].
Process hats one by one. For each hat, iterate over all masks from (1<<n)-1 down to 0 to avoid reusing the same hat in one iteration. For each mask, if person i is not in mask and allows the hat, add dp[mask] to dp[mask | (1<<i)] modulo 10^9+7.
After processing all hats, dp[(1<<n)-1] gives the number of valid assignments. Return it modulo 10^9+7.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.