You are given a tree with N nodes, numbered 0 to N-1. The root node of the tree is node 0. You have to find the value of the tree. This is the same as the value of the root node of the tree. (See explanation below) The tree value can be quite large, so you are asked to give the result modulo 1000000007 (10^9 +7).

Remember that the depth of a node is its distance from the root. So the root node has depth 0, all child nodes of the root node have depth 1; children of these child nodes have depth 2 and so on. Remember also that a leaf node is any node that has no children. The node to which any node is attached, joining it to the tree, is called its parent node.

The value of any leaf node is equal to its depth. For other nodes we need to do a calculation to find the node value. First we find the values of each of their child nodes. We take the biggest of these (p) and the smallest (q). The value of the node is then p^3 * q^2. For example, if a node has three children with values 5, 2 and 7 then p = 7 and q = 2, giving a node value of 7^3 * 2^2 = 1372. For a node with only one child having a value of 3, we have p = 3 and q = 3, giving a node value of 3^3 * 3^2 = 243.

To check that you have understood the problem correctly, the following table gives all of the node values for the tree of 21 nodes (numbered 0 to 20) in the example below.

0  189076013219253356713152 = 273443105 modulo 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

Note that the example has been made deliberately small to assist in explaining the problem. The actual problem will describe a tree which is about 50 times bigger.

Input/Output description: The first line of the input data will contain 2 space-separated integers N and M. N is the number of nodes in the tree. These are numbered 0 to N-1. M lines of data follow. Each of these lines contains 20 space-separated integers. These are the parent nodes of nodes 1, 2, 3, etc. The first line contains the parents of nodes 1 to 20, the second line contains the parents of nodes 21 to 40, and so on until the parents of all nodes in the tree have been read. Your answer is a single integer, the value of the root node (modulo 1000000007).

Example:

input:
21 1
0 1 0 0 0 1 1 0 7 7 7 0 8 12 5 1 12 7 1 12

answer:
273443105

Mathias, Hi

Many thanks for your kind words. I'm glad that you liked the problem.

You may be interested in the following; although I am choosing my words carefully for those who have yet to solve the problem. Those who have solved it will probably understand my comments.

Usually, I have an idea for a problem and then refine it into something usable. In this case I had a concept that I wanted to include within a problem but had no idea what the problem might look like. There was also a need to ensure that special language features would not result in a huge simplification of the problem. This aspect was the biggest hurdle to overcome. The problem took me significantly longer to develop than I had expected. The idea for the tree came quite late in the development. In the end I was pleased to have achieved what I had originally intended to do.

I hope that other colleagues find it a fun problem too.