Problem Statement

Preferred Hat Assignments with Pair Dependencies There are `n` people and hat types numbered from `1` to `40`. Person `i` has a list of hat types that they are willing to wear. Assign exactly one hat to every person. A hat can be assigned to at most one person, and every person must receive a hat from their own preference list. Additionally, whenever an even-numbered hat `h` is assigned, hat `h - 1` must also be assigned to a different person. For example, assigning hat `8` is allowed only if hat `7` is assigned as well. Count the number of valid assignments. Print the answer modulo `1000000007`. Input Format The first line contains an integer `n`. For each person from `1` to `n`, the next line contains an integer `c`, followed by `c` distinct preferred hat numbers. Output Format Print one integer: the number of valid assignments modulo `1000000007`. Constraints - `1 <= n <= 10` - `1 <= c <= 40` - Every preferred hat number is between `1` and `40`. Example Input `2` `2 1 2`