In an undirected graph, a matching is a subset of the edges of the graph such that each vertex of the graph is adjacent to at most one of the selected edges. The maximum matching is a matching of maximum possible cardinality.

You are given a tree with $N$ nodes. Your task is to find the size of the maximum matching and the number of maximum matchings (the latter one modulo $M$).

Constraints

$1\le N\le 1.5\times {10}^6$

$1\le M\le {10}^9$

Subtask 1 [1%]

$1\le N\le 10$

Subtask 2 [4%]

$1\le N\le {10}^3$

Subtask 3 [10%]

$1\le N\le 5\times {10}^4$

Subtask 4 [15%]

$1\le N\le 3\times {10}^5$

Subtask 5 [15%]

$1\le N\le 4\times {10}^5$

Subtask 6 [15%]

$1\le N\le 7\times {10}^5$

Subtask 7 [15%]

$1\le N\le 9\times {10}^5$

Subtask 8 [25%]

No additional constraints.

Input Specification

The first line of input contains an integer $N$ that denotes the number of nodes of the tree. The nodes are numbered $1$ through $N$.

The following $N-1$ lines contain a description of the tree edges. Each of the lines contains two integers $a$ and $b$ that represent an edge connecting the nodes $a$ and $b$.

The last line of input contains an integer $M$.

Output Specification

The first line of output should contain the cardinality of the maximum matching in the tree.

The second line should contain the number of maximum matchings modulo $M$.

Sample Input

5
1 2
3 2
4 5
1 4
17

Sample Output

2
3