{"raw_statement":[{"iden":"background","content":"称一个长度为 $2n$ 的排列 $\\pi$ 是完美匹配，当且仅当其满足\n- $\\forall 1\\le i\\le n,\\pi_{2i-1}<\\pi_{2i}$\n- $\\forall 1\\le i< n,\\pi_{2i-1}<\\pi_{2i+1}$\n\n记 $\\textup{inv }\\pi$ 表示 $\\pi$ 的逆序对数，$\\textup{sgn }\\pi=(-1)^{\\textup{inv }\\pi}$，$\\mathfrak{M}_{2n}$ 表示全体长度为 $2n$ 的完美匹配构成的集合。\n\t\n令 $\\mathbf{A}=(a_{i,j})_{1\\le i<j\\le 2n}$ 是一个反对称矩阵，定义 $\\mathbf{A}$ 的 $\\text{Pfaffian}$ 为\n$$\\textup{Pf}(\\mathbf{A})=\\sum\\limits_{\\pi\\in\\mathfrak{M}_{2n}}(\\textup{sgn }\\pi)\\prod\\limits_{i=1}^{n}a_{\\pi(2i-1),\\pi(2i)}$$"},{"iden":"statement","content":"给定偶数 $n$ 与反对称矩阵 $\\mathbf{A}=(a_{i,j})_{1\\le i<j\\le n}$，求 $\\textup{Pf}(\\mathbf{A})$ 对 $10^9+7$ 取模的结果。"},{"iden":"input","content":"第一行一个正整数 $n$，保证 $n$ 是偶数。\n\n接下来 $n-1$ 行，第 $i$ 行有 $n-i$ 个非负整数，其中第 $j$ 个整数表示 $a_{i,i+j}$。"},{"iden":"output","content":"一行一个非负整数，表示答案。"},{"iden":"note","content":"对于 $30\\%$ 的数据，$n\\le 10$。\n\n对于 $100\\%$ 的数据，$2\\leq n\\le 500$，$0\\le a_{i,j}<10^9+7$。"}],"translated_statement":null,"sample_group":[["4\n1 2 3\n4 5\n6","8"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}