【模板】Pfaffian
题目背景
称一个长度为 $2n$ 的排列 $\pi$ 是完美匹配,当且仅当其满足
- $\forall 1\le i\le n,\pi_{2i-1}<\pi_{2i}$
- $\forall 1\le i< n,\pi_{2i-1}<\pi_{2i+1}$
记 $\textup{inv }\pi$ 表示 $\pi$ 的逆序对数,$\textup{sgn }\pi=(-1)^{\textup{inv }\pi}$,$\mathfrak{M}_{2n}$ 表示全体长度为 $2n$ 的完美匹配构成的集合。
令 $\mathbf{A}=(a_{i,j})_{1\le i<j\le 2n}$ 是一个反对称矩阵,定义 $\mathbf{A}$ 的 $\text{Pfaffian}$ 为
$$\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)}$$
题目描述
给定偶数 $n$ 与反对称矩阵 $\mathbf{A}=(a_{i,j})_{1\le i<j\le n}$,求 $\textup{Pf}(\mathbf{A})$ 对 $10^9+7$ 取模的结果。
输入输出格式
输入格式
第一行一个正整数 $n$,保证 $n$ 是偶数。
接下来 $n-1$ 行,第 $i$ 行有 $n-i$ 个非负整数,其中第 $j$ 个整数表示 $a_{i,i+j}$。
输出格式
一行一个非负整数,表示答案。
输入输出样例
输入样例 #1
4
1 2 3
4 5
6
输出样例 #1
8
说明
对于 $30\%$ 的数据,$n\le 10$。
对于 $100\%$ 的数据,$2\leq n\le 500$,$0\le a_{i,j}<10^9+7$。