There are many fun things to do in preparation for Christmas. Some decorate Christmas trees, others bake gingerbread cookies, and computer scientists like Nella build graphs. In particular, Nella starts off with a collection of nodes. Then, for each node, she chooses one of the other nodes uniformly at random and connects the two nodes with an undirected edge. Note that it is possible for there to be more than one edge between a pair of nodes.
Nella does not want her graph to be too disconnected or it would be too much of a hassle to clean up. Therefore, as her older sibling, you should help her determine the expected number of connected components in her graph.
Subtask 1 [5%]
Subtask 2 [35%]
Subtask 3 [60%]
No additional constraints.
The first and only line contains an integer , the number of nodes in Nella's graph.
Output , where the expected number of connected components in Nella's graph can be expressed as a fraction in lowest terms, and is an integer such that .
Out of all possibilities, of them form a graph with connected component and of them form a graph with connected components. So, the expected number of connected components is .