Solution

If we define $\texttt{dp}[S]$ to be the number of matchings for females in the set $S$ to the first $|S|$ males, this problem boils down to the following:

(The : stands for "such that".) In English, this is equivalent to the following:

The number of matchings in a subset $S$ to include a certain female $x$ is equivalent to the sum of all the matchings without female $x$ where female $x$ is compatible with the $|S|$-th male.

Our base case is the empty set, which has a value of $1$ (the empty set can be considered as a single matching involving zero pairs).

Implementation

Time Complexity: $\mathcal{O}(N\cdot 2^N)$

Copy
MOD = 10**9 + 7
MAX_N = 21

n = int(input())

compat = []
for _ in range(n):
	compat.append(list(map(int, input().split())))

dp = [0] * (1 << n)