Matchings

Memory limit: 32 MB

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 nodes. Your task is to find the size of the maximum matching and the number of maximum matchings (the latter one modulo ).

Input

The first line of input contains an integer that denotes the number of nodes of the tree (). The nodes are numbered through . The following lines contain a description of the tree edges. Each of the lines contains two integers and that represent an edge connecting the nodes and (). The last line of input contains an integer ().

Output

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 .

Example

For the input data:

5
1 2
3 2
4 5
1 4
17

the correct result is:

2
3

Task author: Tomasz Idziaszek.