题目背景

称一个长度为 $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}$。

输出格式

一行一个非负整数，表示答案。

4
1 2 3
4 5
6

8

提示

对于 $30\%$ 的数据，$n\le 10$。

对于 $100\%$ 的数据，$2\leq n\le 500$，$0\le a_{i,j}<10^9+7$。