## DMOPC '21 Contest 4 P4 - Christmas Graph

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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.

#### Input Specification

The first and only line contains an integer , the number of nodes in Nella's graph.

#### Output Specification

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 .

#### Sample Input

4

#### Sample Output

370370374

#### Explanation

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 .