Problem C
Reconstructing Binary Forests

Input: Standard Input

Output: Standard Output

 

Definition 1: A tree is a connected undirected graph with no simple circuits.

Definition 2: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Definition 3: In a rooted tree, if v is a vertex other than root, then the parent of v is the unique node u, such that, there is a directed edge from u to v.

Definition 4: In a rooted tree, the children of a vertex v are the set of vertices, for which, u is the parent.

Definition 5: Ancestor of a vertex other than root are the vertices in the path from root to it’s vertex.

Definition 6: The descendents of a vertex v are those vertices, that have v as an ancestor.

Definition 7: A rooted tree is called full m-ary tree, if every internal vertex has exactly m children.

Definition 8: Height of a node is the length of the path from that to the farthest descendent leaf.

Definition 9: A forest is a graph, which is composed of one or more trees.

 

Given the height of each non leaf node in a forest, find the number of ways to build the forest. All the trees are complete binary tree, and you can assume that, there are always enough leaf nodes to complete the tree.

You have to find the number of trees, when all nodes are of different colors.

Please remember, these two trees are different. But, within a forest, ordering of trees doesn’t matter.

 

Input and Output

Input contains multiple test cases. Each test case, starts with two integers N and M. N is the number of nodes. Next line contains N integers, the height of each non leaf node. Each input is followed by a blank line.

For each test case, output the number of forests when all the node are of different color. Output all number modulo M.

 

Constraints

 

 

Sample Input                                                  Output for Sample Input

2 1000

2 1

 

3 1000

2 1 1

 

2

6

 

Problemsetter: Manzurur Rahman Khan