{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eOne day, three fairies, Sunny, Luna and Star visited Cirno’s house. Cirno was very happy, so she decided to give a present to them.\u003cbr\u003eCirno’s present was a tree with N nodes. Each node of the tree has an equal possibility to be owned by one of Sunny, Luna or Star. After having decided every node’s owner, Cirno cut the edges that connect different owner’s nodes, after which each of the three fairies got some connected component of nodes (possibly none).\u003cbr\u003eThen each of the three fairies had to spend some magical energy repairing the components she got. Suppose she had X components containing odd number of nodes and Y components containing even number of nodes, the magical energy she would spend equals max(0, X - Y ).\u003cbr\u003eCirno would compensate for the energy they spent with some food, so she asked you the expectation of the total energy the three fairies would spend, and your task is to find out the answer.\u003cbr\u003eTo make it simpler, as it’s easy to prove the multiplication of the expectation and the Nth power of three makes an integer, your task is to find the remainder of the multiplication divided by 10\u003csup\u003e9\u003c/sup\u003e + 7.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases, please process till EOF.\u003cbr\u003eEach test case starts with a line containing one integer N (1 \u0026lt;\u003d N \u0026lt;\u003d 300). Then follows N - 1 lines, each contains two integers u and v (1 \u0026lt;\u003d u, v \u0026lt;\u003d N), representing an edge between node u and node v."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the remainder of the product of the expected energy cost and the N-th power of three (actually, the remainder divided by 10\u003csup\u003e9\u003c/sup\u003e + 7) in a line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n1 2\r\n3\r\n2 1\r\n1 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n12\r\n51\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}