{"raw_statement":[{"iden":"problem statement","content":"Given is a tree with $N$ vertices numbered $1$ to $N$, and $N-1$ edges numbered $1$ to $N-1$. Edge $i$ connects Vertex $a_i$ and $b_i$ bidirectionally and has a length of $1$.\nSnuke will paint each vertex white or black. The _niceness_ of a way of painting the graph is $\\max(X, Y)$, where $X$ is the maximum among the distances between white vertices, and $Y$ is the maximum among the distances between black vertices. Here, if there is no vertex of one color, we consider the maximum among the distances between vertices of that color to be $0$.\nThere are $2^N$ ways of painting the graph. Compute the sum of the nicenesses of all those ways, modulo $(10^{9}+7)$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^{5}$\n*   $1 \\leq a_i, b_i \\leq N$\n*   The given graph is a tree."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$"},{"iden":"sample input 1","content":"2\n1 2"},{"iden":"sample output 1","content":"2\n\n*   If we paint Vertex $1$ and $2$ the same color, the niceness will be $1$; if we paint them different colors, the niceness will be $0$.\n*   The sum of those nicenesses is $2$."},{"iden":"sample input 2","content":"6\n1 2\n2 3\n3 4\n4 5\n3 6"},{"iden":"sample output 2","content":"224"},{"iden":"sample input 3","content":"35\n25 4\n33 7\n11 26\n32 4\n12 7\n31 27\n19 6\n10 22\n17 12\n28 24\n28 1\n24 15\n30 24\n24 11\n23 18\n14 15\n4 29\n33 24\n15 34\n11 3\n4 35\n5 34\n34 2\n16 19\n7 18\n19 31\n22 8\n13 26\n20 6\n20 9\n4 33\n4 8\n29 19\n15 21"},{"iden":"sample output 3","content":"298219707\n\n*   Be sure to compute the sum modulo $(10^{9}+7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}