Beautiful Graph

You are given an integer $N$.

A complete graph has exactly one undirected edge between every pair of distinct vertices.

A graph is beautiful when it meets both conditions below.

• It is a complete graph on $N$ vertices.
• Every edge has cost $1$ or cost $2$.

So there are $2^{N(N-1)/2}$ beautiful graphs.

A minimum spanning tree (MST) of a beautiful graph $G$ is a subgraph that meets these conditions.

• It contains all $N$ vertices of $G$.
• It is connected, so a path joins every pair of its vertices.
• The sum of the costs of its edges is minimum.

One beautiful graph can have several MSTs. Their costs are all equal.

An MST is a line when every vertex in it has degree at most $2$.

Let $f(G)$ be the number of MSTs of a beautiful graph $G$ that are lines.

Print the sum of $f(G)$ over all beautiful graphs $G$ on $N$ vertices, modulo 1,000,000,007.

The first line contains $N$. ($2 \le N \le 16$)

Print the answer on the first line.