Description

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

Format

Input

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

Output

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

Samples

5
1 2
3 2
4 5
1 4
17

2
3

Limitation

【数据范围】

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