Background

A permutation $\pi$ of length $2n$ is called a perfect matching if and only if it satisfies:

• $\forall 1\le i\le n,\ \pi_{2i-1}<\pi_{2i}$.
• $\forall 1\le i< n,\ \pi_{2i-1}<\pi_{2i+1}$.

Let $\textup{inv }\pi$ denote the number of inversions of $\pi$, and $\textup{sgn }\pi=(-1)^{\textup{inv }\pi}$. Let $\mathfrak{M}_{2n}$ be the set of all perfect matchings of length $2n$.

Let $\mathbf{A}=(a_{i,j})_{1\le i<j\le 2n}$ be a skew-symmetric matrix. The $\text{Pfaffian}$ of $\mathbf{A}$ is defined as

$$\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)}$$

Problem Description

Given an even integer $n$ and a skew-symmetric matrix $\mathbf{A}=(a_{i,j})_{1\le i<j\le n}$, find $\textup{Pf}(\mathbf{A}) \bmod (10^9+7)$.

Input Format

The first line contains a positive integer $n$, and it is guaranteed that $n$ is even.

The next $n-1$ lines describe the matrix. On the $i$-th line, there are $n-i$ non-negative integers, where the $j$-th integer represents $a_{i,i+j}$.

Output Format

Output one non-negative integer, the answer.

4
1 2 3
4 5
6

8

Hint

For $30\%$ of the testdata, $n\le 10$.

For $100\%$ of the testdata, $2\le n\le 500$, $0\le a_{i,j}<10^9+7$.

Translated by ChatGPT 5