Description

给定一棵树，求他的最大匹配和最大匹配的方案数(mod m)。

Input

第一行一个整数N，表示节点个数。
接下来N-1行每行两个数x y，表示这棵树的一条边。
最后一行一个整数M，表示模数。

Output

两行，第一行是最大匹配，第二行是方案数。

Sample Input

Sample Output

Hint

【数据范围】

N<=15*10^5，M<=10^9。

Source