Description

给定偶数 $n$ 与反对称矩阵 $\mathbf{A}=(a_{i,j})_{1\le i<j\le n}$，求 $\textup{Pf}(\mathbf{A})$ 对 $10^9+7$ 取模的结果。

Input Format

第一行一个正整数 $n$，保证 $n$ 是偶数。

接下来 $n-1$ 行，第 $i$ 行有 $n-i$ 个非负整数，其中第 $j$ 个整数表示 $a_{i,i+j}$。

Output Format

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

4
1 2 3
4 5
6

8

Hint

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

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