{"problem":{"name":"D. Forest Game","description":{"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: Please ca","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10123D"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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 \n\n## Output\n\nOutput one number: the expected value of the final score of this boring game multiplied by N!, modulo 109 + 7.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10123D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}