Many thanks to Clive Fraser for creating this problem!
You are given a tree with N nodes, numbered 0 to N-1. The root node of the tree is node 0.
You have been asked to paint the tree by painting each of its nodes. However, you must not paint two nodes the
same colour if they are close together. Specifically, adjacent nodes cannot be painted the same colour and nodes
which are separated by exactly one other node cannot be painted the same colour. Consider a strip of connected
nodes within the tree. An example is shown below:
-- A -- B -- C -- D -- E -- F -- G --
Node D cannot have the same colour as either of its immediate neighbours C and E. Also, node D cannot
have the same colour as either node B or node F as these are separated from D by exactly one other node.
You have to paint the tree while observing these restrictions. Given the maximum number of colours available,
you are asked to find the number of different ways in which the tree can be painted. This value can be quite large,
so you are asked to give the result modulo 1000000007 (10^9 +7).
The example below has been made deliberately small to ensure that you have understood the problem correctly
(see Input/Output description for details). The example has just 21 nodes (0 to 20). The main data line
shows that node 1 is connected to node 0, node 2 to node 1, node 3 to node 0, ..., node 13 to
node 8, node 14 to node 12, ... , and finally node 20 to node 12. The actual problem will describe a
tree which is about 50 times larger.
Input/Output description: The first line of the input data will contain 3 space-separated integers N, C
and M.
N is the number of nodes in the tree. These are numbered 0 to N-1.
C is the number of available colours.
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 number of different ways of painting the tree (modulo 1000000007).
Example:
input:
21 7 1
0 1 0 0 0 1 1 0 7 7 7 0 8 12 5 1 12 7 1 12
answer:
863999244 ( = 108864000000 modulo 1000000007)