Muchii Permutate

You are given a tree with $N$ nodes (numbered from $1$ to $N$), and we consider its edges numbered from $1$ to $N - 1$ (in the order in which they are given in the input). A tree is a connected, acyclic, undirected graph.

Let $P$ be a permutation of the numbers from $1$ to $N - 1$. For this given permutation $P$, we assign to each edge of index $i$ a weight equal to $P[i]$. Then, consider an algorithm in which we initially have no edges in the tree, and we start adding them one by one, in the order of their numbering (essentially in the order in which they are given in the input, from $1$ to $N - 1$ — the order of addition does not depend on the weights).

For the permutation $P$ to be considered valid, it is required that at every step of the algorithm, any maximal connected component (with at least $2$ nodes) formed so far has only edges with consecutive weights — here the components are considered individually (and only the maximal ones), so all of them must satisfy this condition, at every step of the algorithm.

Requirement

Given the number $N$, representing the number of nodes in the tree, as well as the $N - 1$ edges of the tree (in the order given in the statement), determine the minimum number of inversions of a valid permutation, as well as the number of valid permutations that achieve this minimum (modulo $10^9 + 7$).

Implementation Details

You must implement a single function:

std::pair<long long, int> solve(int N, std::vector<int> U, std::vector<int> V);

which receives as parameters:

• $N$, the number of nodes in the tree
• The sequences $U$ and $V$, where the pair $U[i], V[i]$ represents the endpoints of edge $i + 1$ in the tree (according to the numbering given in the statement), for $i$ from $0$ to $N - 2$.

The solve function will be called exactly once.

Constraints

• $2 \leq N \leq 500 \ 000$
• $1 \leq U_i, V_i \leq N$, for $0 \leq i \leq N - 2$
• Note: Only the number of valid permutations with a minimum number of inversions is computed modulo $10^9 + 7$. The minimum number of inversions itself is computed as an exact value.

Example 1

input

7
3 7
2 5
2 6
1 3
1 2
2 4

stdout

2 2

Explanation

For the first example, the two optimal valid permutations that satisfy the constraints and achieve the minimum of $2$ inversions are:

• $P = (1, 3, 4, 2, 5, 6)$
• $P = (3, 1, 2, 4, 5, 6)$

Example 2

input

20
16 17
4 5
8 9
11 12
18 19
1 2
14 15
7 8
19 20
6 7
15 16
3 4
12 13
9 10
2 3
17 18
5 6
10 11
13 14

output

48 8

Explanation

For the second example, the minimum number of inversions of a valid permutation is $48$, and there are $8$ valid permutations with this minimum number of inversions.