{"problem":{"name":"Matching","description":{"content":"There are $N$ men and $N$ women, both numbered $1, 2, \\ldots, N$. For each $i, j$ ($1 \\leq i, j \\leq N$), the compatibility of Man $i$ and Woman $j$ is given as an integer $a_{i, j}$. If $a_{i, j} = 1","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_o"},"statements":[{"statement_type":"Markdown","content":"There are $N$ men and $N$ women, both numbered $1, 2, \\ldots, N$.\nFor each $i, j$ ($1 \\leq i, j \\leq N$), the compatibility of Man $i$ and Woman $j$ is given as an integer $a_{i, j}$. If $a_{i, j} = 1$, Man $i$ and Woman $j$ are compatible; if $a_{i, j} = 0$, they are not.\nTaro is trying to make $N$ pairs, each consisting of a man and a woman who are compatible. Here, each man and each woman must belong to exactly one pair.\nFind the number of ways in which Taro can make $N$ pairs, modulo $10^9 + 7$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 21$\n*   $a_{i, j}$ is $0$ or $1$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_{1, 1}$ $\\ldots$ $a_{1, N}$\n$:$\n$a_{N, 1}$ $\\ldots$ $a_{N, N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_o","tags":[],"sample_group":[["3\n0 1 1\n1 0 1\n1 1 1","3\n\nThere are three ways to make pairs, as follows ($(i, j)$ denotes a pair of Man $i$ and Woman $j$):\n\n*   $(1, 2), (2, 1), (3, 3)$\n*   $(1, 2), (2, 3), (3, 1)$\n*   $(1, 3), (2, 1), (3, 2)$"],["4\n0 1 0 0\n0 0 0 1\n1 0 0 0\n0 0 1 0","1\n\nThere is one way to make pairs, as follows:\n\n*   $(1, 2), (2, 4), (3, 1), (4, 3)$"],["1\n0","0"],["21\n0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1\n1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0\n0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1\n0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0\n1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0\n0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1\n0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0\n0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1\n0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1\n0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1\n0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0\n0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1\n0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1\n1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1\n0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1\n1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0\n0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1\n0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1\n0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0\n1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0\n1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0","102515160\n\nBe sure to print the number modulo $10^9 + 7$."]],"created_at":"2026-03-03 11:01:14"}}