1229. Count Ways to Assign Tasks to Workers

Given a square compatibility matrix compat where compat[i][j] is 1 if task i can be assigned to worker j, count the ways to assign every task to a distinct worker (a perfect matching). The input is JSON {compat}.

Input: JSON {compat}.

Output: Integer — the number of valid assignments.

Examples

Input: {"compat":[[1,1,0],[0,1,1],[1,0,1]]}
Output: 2
Explanation: Two perfect matchings exist.

Input: {"compat":[[1]]}
Output: 1
Explanation: One assignment.

Input: {"compat":[[0]]}
Output: 0
Explanation: No valid assignment.

Constraints

• 1<=n<=15

Asked by