描述

Freda 看了Tom&Jerry 动画片之后,决定去和一群可爱的mice 玩猫捉老鼠游戏。可是艺术毕竟高于生活,现
实中,相对于一群弱小的mice,强大的Freda 占了优势,每次Freda 都能把这些小鼠们一一抓获。Rainbow 觉得,
Freda 这么做太不公平了!于是,Rainbow 扮演了MiceProtector 的角色。Ta 给这n 只小鼠从1~n 编号,又给Freda
画了一张表示关系的有向图,点a 和点b 之间有边表示Freda 在没抓到小鼠a 时不能去抓小鼠b. 当然,这难不
倒Freda,只需要作一下拓扑排序就可以了。不过,Rainbow 和Freda 都想知道,Freda 到底有多少不同的方式抓
到所有小鼠呢?由于这个数可能很大,你只需要输出它mod p 的值。

输入格式

第一行用空格隔开的两个整数n,p,表示小鼠的数量和需要mod 的数字。
接下来n-1 行每行用空格隔开的两个整数a,b,表示在关系图里存在由a 到b 的一条边。

输出格式

一行一个整数,表示Freda 能够按Rainbow 的要求抓到这些小鼠的不同方案数mod p 的值。

样例输入

4 100000007
1 2
1 3
2 4

样例输出

3

数据范围与约定

对于30%的数据,n<=20.
对于100%的数据,1<=n<=1500000,p 为质数,n<p<2^31,保证图是一棵有根树.

样例解释

有如下三种不同的顺序:
1、1->2->3->4
2、1->2->4->3
3、1->3->2->4