Pfaffian Modulo

Given an even integer \( n \) and a skew-symmetric matrix \( \mathbf{A}=(a_{i,j})_{1\le i<j\le n} \), compute the Pfaffian \( \text{Pf}(\mathbf{A}) \) modulo \( 10^9+7 \). Recall that for a skew-symmetric matrix, \( \text{Pf}(\mathbf{A})^2 = \det(\mathbf{A}) \).

inputFormat

The input begins with an even integer \( n \) (\(2\le n\le 10^3\) for example). Following this, there are \( n-1 \) lines. The \( i \)-th line (1-indexed) contains \( n-i \) space-separated integers, representing \( a_{i,i+1}, a_{i,i+2}, \ldots, a_{i,n} \). Note that since \( \mathbf{A} \) is skew-symmetric, we have \( a_{j,i} = -a_{i,j} \) and \( a_{i,i}=0 \) for all \( i,j \).

outputFormat

Output a single integer: the value of \( \text{Pf}(\mathbf{A}) \) modulo \( 10^9+7 \).

sample

2
3

3