Counting Edge-Destroying Ways to Retain a Strongly Connected Digraph

In response to the call to promote mainstream values, everyone decided to fill the class with love. In a class there are n boys. If person a loves person b, then we say that there is a directed edge (a\rightarrow b) between them. The class is considered to be full of love if the directed graph on these n nodes is strongly connected (i.e. for any two nodes, each can reach the other).

Unfortunately, some misfortune occurs and every edge may be destroyed. As the messenger of love, you are to determine in how many ways some subset of the edges can be destroyed (i.e. removed) such that the remaining graph is still strongly connected. In other words, count the number of edge subsets whose removal leaves a strongly connected graph over the complete directed graph on n nodes (where every possible directed edge (a\rightarrow b) for (a\neq b) initially exists).

Note: All formulas are given in ( \LaTeX ) format.

inputFormat

The input consists of one integer n ((1 \leq n \leq 9)).

outputFormat

Output one integer: the number of ways to remove a subset of the edges from the complete directed graph on n nodes such that the remaining graph is strongly connected.

sample

1

1