Counting Labeled Connected Graphs

Given an integer n, count the number of labeled undirected connected graphs with n nodes.

The number of all labeled graphs with n nodes is given by \(2^{\binom{n}{2}}\). A graph is connected if there exists a path between every pair of vertices. One way to compute the number of connected graphs \(c(n)\) is via the recurrence:

\[ c(n) = 2^{\binom{n}{2}} - \sum_{k=1}^{n-1} \binom{n-1}{k-1} \; c(k) \; 2^{\binom{n-k}{2}}, \] where \(c(1)=1\). Note that \(\binom{n}{2} = \frac{n(n-1)}{2}\).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10), representing the number of nodes.

outputFormat

Output a single number representing the number of labeled undirected connected graphs with n nodes.

sample

1

1