{"raw_statement":[{"iden":"problem statement","content":"You are given a tree with $N$ vertices and $N-1$ edges. The vertices are numbered $1$ to $N$, and the $i$\\-th edge connects Vertex $a_i$ and $b_i$.\nYou have coloring materials of $K$ colors. For each vertex in the tree, you will choose one of the $K$ colors to paint it, so that the following condition is satisfied:\n\n*   If the distance between two different vertices $x$ and $y$ is less than or equal to two, $x$ and $y$ have different colors.\n\nHow many ways are there to paint the tree? Find the count modulo $1\\ 000\\ 000\\ 007$.\n\nWhat is tree? A tree is a kind of graph. For detail, please see: [Wikipedia \"Tree (graph theory)\"](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6))\n\nWhat is distance? The distance between two vertices $x$ and $y$ is the minimum number of edges one has to traverse to get from $x$ to $y$."},{"iden":"constraints","content":"*   $1 \\leq N,K \\leq 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$ $K$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$.$\n$.$\n$.$\n$a_{N-1}$ $b_{N-1}$"},{"iden":"sample input 1","content":"4 3\n1 2\n2 3\n3 4"},{"iden":"sample output 1","content":"6\n\n![image](https://img.atcoder.jp/ghi/491cd56a53e99ba7677ee4827b8f767a.png)\nThere are six ways to paint the tree."},{"iden":"sample input 2","content":"5 4\n1 2\n1 3\n1 4\n4 5"},{"iden":"sample output 2","content":"48"},{"iden":"sample input 3","content":"16 22\n12 1\n3 1\n4 16\n7 12\n6 2\n2 15\n5 16\n14 16\n10 11\n3 10\n3 13\n8 6\n16 8\n9 12\n4 3"},{"iden":"sample output 3","content":"271414432"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}