Лёша увидел во сне следующую задачу. Дано дерево (неориентированный связный граф без циклов). Нужно посчитать количество способов покрасить вершины графа в не более чем $$$k$$$ цветов так, чтобы любые две соединённые ребром вершины имели разный цвет. Два способа считаются различными, если найдётся хотя бы одна вершина, которая будет покрашена в разные цвета.
Проснувшись, Лёша захотел решить эту задачу. Помогите ему.
В первой строке вводятся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 10^6$$$) — количество вершин в дереве и количество цветов.
В следующих $$$n - 1$$$ строках описываются рёбра дерева. В $$$i$$$-й строке вводится целое число $$$p_i$$$ ($$$1 \le p_i \lt i$$$) — номер предка вершины с номером $$$i$$$ (для $$$i$$$ от $$$2$$$ до $$$n$$$ включительно).
Вершины пронумерованы с $$$1$$$ до $$$n$$$, а корень дерева находится в вершине $$$1$$$.
В единственной строке выведите количество способов покрасить вершины данного дерева в $$$k$$$ цветов по модулю $$$10^9 + 9$$$.
4 3113
24
10 35318122215562
402784325
Объём входных данных в данной задаче велик, поэтому при написании решения настоятельно рекомендуется использовать оптимизации ввода/вывода.
