n people is going to a conference. The organisers print badges in 40 colours numbered from 1 to 40, and each colour can go to one person only. likes[i] is the list of colours the i-th person is willing to wear.
Count the ways to give every person exactly one badge so that each gets a colour from their own list and no two people get the same colour. Two ways differ if at least one person gets a different colour. The answer can be large, so return it modulo 10⁹ + 7.likes=[[2, 7], [7], [1, 2]] → 1
The second person must get 7, so the first gets 2 and the third is left with 1. There is one way.
likes=[[5, 6], [5, 6, 9]] → 4
The pairs (5, 6), (5, 9), (6, 5) and (6, 9): 4 ways.
likes=[[3], [3], [1, 2]] → 0
The first two both accept only colour 3, and nobody may share a badge.
n = len(likes)n ≤ 10len(likes[i]) ≤ 40likes[i][j] ≤ 40likes[i]likes=[[2, 7], [7], [1, 2]]
1
Run checks the first 3 tests in your browser. Submit checks all 79 tests on the server, hidden ones included.