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