{"raw_statement":[{"iden":"statement","content":"Consider the following boring game about removing nodes from a forest. Initially, the forest contains only one tree with N nodes, and your initial score is 0. The game then goes as follows:\n\nPlease calculate the expected value of your final score multiplied by N!, modulo 109 + 7.\n\nThe first line of input contains one integer N indicating the number of nodes in the initial tree.\n\nEach of the following N - 1 lines contains two integers x and y, indicating that x-th node and y-th node are connected by an edge in the given tree. The nodes are numbered from 1 to N.\n\nOutput one number: the expected value of the final score of this boring game multiplied by N!, modulo 109 + 7.\n\n"},{"iden":"input","content":"The first line of input contains one integer N indicating the number of nodes in the initial tree.Each of the following N - 1 lines contains two integers x and y, indicating that x-th node and y-th node are connected by an edge in the given tree. The nodes are numbered from 1 to N.  1 ≤ N ≤ 105  1 ≤ x, y ≤ N  the given graph is a tree "},{"iden":"output","content":"Output one number: the expected value of the final score of this boring game multiplied by N!, modulo 109 + 7."},{"iden":"examples","content":"Input21 2Output6Input31 22 3Output34"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of nodes in the initial tree.  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, N\\} $ and $ |E| = N - 1 $.  \n\nLet $ \\sigma \\in S_N $ be a uniformly random permutation of the nodes (representing a random removal order).  \nLet $ S(\\sigma) $ be the final score after removing nodes in order $ \\sigma $, where at each step, removing a node contributes $ 1 $ to the score if and only if it is a leaf at the time of removal.  \n\n**Constraints**  \n- $ 1 \\leq N \\leq 10^5 $  \n- The graph is a tree.  \n\n**Objective**  \nCompute:  \n$$\n\\mathbb{E}[S(\\sigma)] \\cdot N! \\mod (10^9 + 7)\n$$  \nwhich is equivalent to:  \n$$\n\\sum_{\\sigma \\in S_N} S(\\sigma) \\mod (10^9 + 7)\n$$","simple_statement":"You are given a tree with N nodes. In each step, you randomly remove a node and add the size of its connected component to your score. The process continues until all nodes are removed. Calculate the expected score multiplied by N!, modulo 10^9+7.","has_page_source":false}