Consider this problem:

There are two sets of N elements each, 1 <= N <= 21. I need to pair each element from set #1 to a distinct element of set #2 with restrictions. Input also contains a matrix where the value at row i, column j is 1 if the ith element of set #1 can be matched with the jth element of set #2. If it can’t be matched the value is 0. Find how many ways there are to make the N pairs of elements mod 10^9+7.

Example input (first line is N, next N lines are the matrix, one row per line)

3
0 1 1
1 1 1
1 1 1

Example output

4

Example input:

3
1 1 1
1 1 1
1 1 1

Example output:

6

I don’t know where to start on this one. Trying all possible matching orders will take forever and I could run out of memory. I think it could be dynamic programming. How to solve this?