Allen, having graduated from the MOO Institute of Techcowlogy (MIT), has started a startup! Allen is the president of his startup. He also hires other employees, each of which is assigned a direct superior. If is a superior of and is a superior of then also is a superior of . Additionally, there are no and such that is the superior of and is the superior of . Allen himself has no superior. Allen is employee number , and the others are employee numbers through .
Finally, Allen must assign salaries to each employee in the company including himself. Due to budget constraints, each employee’s salary is an integer between and . Additionally, no employee can make strictly more than his superior.
Help Allen find the number of ways to assign salaries. As this number may be large, output it modulo .
The first line of the input contains two integers and (, ).
The remaining lines each contain a single positive integer, where the line contains the integer (). denotes the direct superior of employee .
In the first sample case, employee and report directly to Allen. The three salaries, in order, can be , , , or .
In the second sample case, employee reports to Allen and employee reports to employee . In order, the possible salaries are , , , , , , , , , .