{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/9855427dc4ed336602508d8c33ed00ff?v\u003d1714692811\" alt\u003d\"/problems/kingscolors/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003eFar, far away, there is the mystical Kingdom of Trees\n (more formally, “Royal Commonwealth of Connected Undirected\n Simple Acyclic Graphs”). The King there is very sad because his\n kingdom is not accepted as a sovereign state in the United\n Nations. In order to become a member, he needs to make a flag\n the UN can put on their website.\n \u003cp\u003eThe flag will of course consist of the King’s favorite tree,\n which contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e nodes.\n The King would be happy to just have the tree colored in black\n and white, but for the sake of his wife the Queen, he decided\n that the tree will contain all the favorite colors of their\n \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e children (they all\n have distinct favorite colors). Clearly, no two neighboring\n nodes can have the same color, but otherwise any coloring of\n the tree using exactly the \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e colors would make a feasible flag\n candidate.\u003c/p\u003e\n \u003cp\u003eHow many different flags are possible?\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\le k \\le n \\le 2\\, 500$\u003c/span\u003e), where \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e is the number of nodes in the\n King’s favorite tree and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e is the number of children. Then\n follow \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e lines\n describing the edges in the tree; the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e’th of these lines contains a\n non-negative integer \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i \u0026lt;\n i$\u003c/span\u003e, meaning that node \u003cspan class\u003d\"tex2jax_process\"\u003e$p_\n i$\u003c/span\u003e is the parent of \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eThe nodes are numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e and the tree is rooted at node\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e. Note that the\n embedding of the tree on the flag is already fixed, the only\n thing that remains is to assign colors.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput the number of different possible color assignments.\n The number can be quite big, so the King has requested to know\n the answer modulo \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\, 000\\,\n 000\\, 007$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e4 3\n0\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e6 4\n0\n1\n1\n3\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e600\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}