# 字典序最大的树标号

预估时间限制：2.5 秒。内存限制：512 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $4$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

该倍率为静态排序补充解法保留至少两倍实测余量。

## 背景故事

展馆准备在一棵树上挂上亮度各异的灯。每盏灯都要比祖先更亮，同时希望按照结点编号检查时，尽早看到尽可能亮的灯。

(本故事由GPT-6重写)

## 形式化问题描述

给定一棵有 $N$ 个结点、以 $K$ 为根的树，结点编号为 $1,\ldots,N$ .将整数 $1,\ldots,N$ 各使用一次，给结点赋标号 $a_1,\ldots,a_N$ .要求每个非根结点的标号严格大于父亲的标号。

在所有合法方案中，使数组 $(a_1,\ldots,a_N)$ 字典序最大：在第一个不同的结点编号处，标号较大的方案更大。

设最优排列的零起算康托排名为

$$R=\sum_{i=1}^{N} c_i (N-i)!,\qquad c_i=\#\{j:i<j\le N,\ a_j<a_i\}$$

即将全部 $N!$ 个排列按字典序升序排列后，它前面有多少个排列。输出 $R$ 分别对 $100000007$ 和 $100000009$ 取模的结果。

## 输入格式

第一行两个整数 $N,K$ .接下来 $N-1$ 行，每行两个整数 $u,v$ ，表示一条树边。

## 输出格式

输出一行两个整数，依次为上述两个模值，不输出标号排列本身。

## 样例

### 样例 1

### 输入

```text
5 1
1 2
2 3
2 5
3 4
```

### 输出

```text
3 3
```

### 样例 2

### 输入

```text
5 4
4 2
4 3
4 1
5 4
```

### 输出

```text
118 118
```

### 样例 3

### 输入

```text
4 3
3 4
4 1
1 2
```

### 输出

```text
16 16
```

## 样例解释

前两组最优标号数组分别为 $(1,2,4,5,3)$ 和 $(5,4,3,1,2)$ ，零起算排名分别为三和一百一十八。第三组是一条以三为根的链，其唯一标号数组为 $(3,4,1,2)$ ，排名十六。

## 数据范围与保证

$2\le N\le500000$ , $1\le K,u,v\le N$ . 输入边恰好构成一棵树。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |