Цена Дерева

Эта задачу любезно предоставил наш коллега Клайв Фрэйзер aka CSFPython - спасибо большое!

Нам дано дерево с N узлами, пронумерованными от 0 до N-1. Корень дерева в вершине 0. Требуется сосчитать цену дерева - она равна цене "корня" - (о том как расчитываются цены узлов - ниже). Дерево может быть очень большим, так что результат нужно предоставить по модулю 1000000007 (10^9 + 7).

Мы помним что "глубина" узла - это расстояние его от корня. Сам корневой узел имеет глубину 0, растущие из него дочерние узлы - глубину 1; дочерние к этим дочерним - соответственно 2 и так далее. Помним так же что "листом" называется узел не имеющий дочерних. Ну и "родительским" узлом для данного называется тот, кому данный приходится "дочерним".

Цена для узлов определяется очень просто:

• если узел является "листом", то его цена равна его глубине
• для остальных узлов цена зависит от цен дочерних - а именно, мы выбираем дочерний узел с максимальной (p) и минимальной (q) ценой - и цена "родительского" будет p^3 * q^2.

Например, если у узла три дочерних с ценами 5, 2 и 7 то p = 7 и q = 2, и цена родительского будет 7^3 * 2^2 = 1372. Для узла с единственным потомком, например, ценой 3, мы считаем p = 3 и q = 3, так что цена будет 3^3 * 3^2 = 243.

Чтобы проверить что описание понято корректно, рассмотрите следующий пример - здесь номера узлов и их цены. Структура же этого дерева задана ниже в примере. Всего 21 узел (пронумерованные от 0 до 20).

0  189076013219253356713152 = 273443105 по модулю 1000000007
1  57395628
2  2
3  1
4  1
5  32
6  2
7  243
8  32
9  3
10 3
11 3
12 32
13 2
14 2
15 2
16 2
17 2
18 3
19 2
20 2

Отметим что этот пример нарочно сделан небольшим - для решения же задачи будет дано дерево примерно в 50 раз больше.

Входные данные и Ответ

В первой строке два значения через пробел -N and M.
N это размер дерева - то есть количество узлов в нём, напомним, нумеруются они от 0 до N-1.
M это количество последующих строк. Каждая строка содержит 20 целых чисел разделенных пробелами. Это номера "родителей" для узлов 1, 2, 3, и т.д. То есть в первой строке родители к узлам от 1 до 20, во второй - к узлам от 21 до 40, и так далее.

Ваш ответ должен быть единственным целым числом - ценой корневого узла (по модулю 1000000007).

Пример:

входные данные:
21 1
0 1 0 0 0 1 1 0 7 7 7 0 8 12 5 1 12 7 1 12

ответ:
273443105