Spanning Tree Count in Extended Neighbor Graph

Given an integer n representing the number of vertices, consider a graph whose vertices are arranged in a single chain (i.e. in a line) with labels 1,2,...,n. In this graph, an (undirected) edge is placed between two vertices i and j if and only if

\( 1 \le |i-j| \le 3 \).

Your task is to compute the number of spanning trees of this graph.

A standard way to compute the number of spanning trees of any graph is via Kirchhoff's Matrix Tree Theorem. Define the n \times n Laplacian matrix \(A = \{a_{i,j}\}\) by

[ a_{i,j} = \begin{cases} d_i, & \text{if } i=j,\ -1, & \text{if vertices } i \text{ and } j \text{ are adjacent (i.e. }1\le |i-j|\le 3\text{)}, \ 0, & \text{otherwise.} \end{cases} ]

Then remove the n-th row and n-th column to obtain a \((n-1)\times(n-1)\) matrix \(B\). According to Kirchhoff's Matrix Tree Theorem, the number of spanning trees of the graph is exactly \(\det(B)\).

Note: For a vertex \(i\) (where \(1 \le i \le n-1\)), its degree d_i is given by the number of neighbors in the full graph, which is \[ d_i = \min(i,3) + \min(n-i,3). \] You may assume that \(n\) is small (for example, \(1 \le n \le 30\)) so that the answer fits in conventional integer types.

inputFormat

The input consists of a single integer n (\(1 \le n \le 30\)) on one line representing the number of vertices.

outputFormat

Output a single integer: the number of spanning trees in the graph.

sample

1

1