DMOPC '21 Contest 4 P4 - Christmas Graph

View as PDF

Submit solution

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

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 N 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.


2 \le N \le 10^6

Subtask 1 [5%]

2 \le N \le 8

Subtask 2 [35%]

2 \le N \le 3 \times 10^3

Subtask 3 [60%]

No additional constraints.

Input Specification

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

Output Specification

Output PQ^{-1} \bmod 10^9 + 7, where the expected number of connected components in Nella's graph can be expressed as a fraction \dfrac{P}{Q} in lowest terms, and Q^{-1} is an integer such that QQ^{-1} \equiv 1 \pmod{10^9 + 7}.

Sample Input


Sample Output



Out of all 81 possibilities, 78 of them form a graph with 1 connected component and 3 of them form a graph with 2 connected components. So, the expected number of connected components is \dfrac{78}{81} \times 1 + \dfrac{3}{81} \times 2 = \dfrac{28}{27}.


There are no comments at the moment.