1384. Count Ways to Assign Tasks — K Workers

There are k workers and n tasks, with allowed[i][j] equal to 1 when worker i is capable of task j. Every task must be given to a distinct capable worker, and a worker handles at most one task. Count the number of such assignments modulo 1000000007.

Input: A JSON object {"allowed": [[0/1 capability flags per task], ...]} with one row per worker.

Output: Return the number of valid assignments modulo 1000000007.

Examples

Input: {"allowed":[[1,1],[1,1],[1,1]]}
Output: 6
Explanation: Any two distinct workers in order give six assignments.

Input: {"allowed":[[1,0],[0,1],[1,1]]}
Output: 3
Explanation: Capability limits reduce the number of valid assignments.

Constraints

• 1 <= k <= 16
• 1 <= n <= k
• allowed[i][j] is 0 or 1

Asked by