该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

负责人

• 035966_L3

注意

本题的样例没有放在子任务 0 中，而是放在了其他地方：

其中样例 1 会被评测三次。

本题的子任务依赖关系如下：

本题需要使用文件读写（garbage.in / garbage.out）。

在本题中，两个操作序列分别为 $\bm {\{a_i\}}$ 和 $\bm {\{b_j\}}$ 的清理方案本质不同，当且仅当 $\bm {\{a_i\}}$ 和 $\bm {\{b_j\}}$ 满足以下两个条件中的任意一个：

• $\bm {i \ne j}$。
• 存在 $\bm {1 \le k \le \min\{i,j\}}$ 使得 $\bm {a_k \ne b_k}$。

题目背景

Sleeping Goose 是 Sleeping Cup 王国的垃圾站总管理员。

近几年来，随着垃圾站数量的不断增加，Sleeping Goose 深感力不从心。

为了更好地管理 Sleeping Cup 王国的垃圾站，它招募了一些员工。

不幸的是，这些员工经常玩忽职守……

题目描述

Sleeping Cup 王国共有 $n$ 个垃圾站，其中 $1$ 号垃圾站是总垃圾站，而 $2,3,\ldots,n$ 号垃圾站都是分垃圾站。每个分垃圾站都有恰好一个编号小于自己的直接上级垃圾站。

这天上午，Sleeping Goose 查看了所有垃圾站的监控，数出了每个垃圾站目前堆放的垃圾袋数（均为不大于 $n$ 的正整数），并决定让它的员工们对所有垃圾站进行一次大清理。

根据 Sleeping Goose 对员工们的上岗培训内容，Sleeping Goose 需要提供一个操作序列 $\{c_k\}$ 并保证 $1 \le c_i \le n$，而员工们需要升序枚举 $i=1,2,\ldots,k$ 并对每个 $i$ 执行以下操作：

• 如果 $c_i=1$，什么都不做。
• 否则，将 $c_i$ 号垃圾站中的所有垃圾运送到它的直接上级垃圾站。

员工们完成任务后，$1$ 号垃圾站中的所有垃圾将被 Sleeping Goose 亲自拉到垃圾处理厂集中处理。

不幸的是，就像题目背景中说的那样，这些员工经常玩忽职守 —— Sleeping Goose 越让他们干活，他们就越要摸鱼。具体来说，员工们实际上会升序枚举 $i=1,2,\ldots,k$ 并对每个 $i$ 执行以下操作：

• 如果 $c_i=1$，什么都不做。
• 如果 $c_i$ 号垃圾站中目前存放的垃圾袋数不大于 $i$，什么都不做。
• 如果以上两个条件都不满足，保留 $c_i$ 号垃圾站中的 $i$ 袋垃圾，并将剩下的垃圾运送到它的直接上级垃圾站。

尽管如此，Sleeping Goose 还是希望能在这次大清理中用尽量短的时间清理尽量多的垃圾。

为了帮助 Sleeping Goose，你需要回答以下三个问题：

1. Sleeping Goose 在这次大清理中最多能清理多少袋垃圾？
2. 在清理垃圾最多的前提下，Sleeping Goose 给员工们的操作序列至少要包含多少项？
3. 在清理垃圾最多且（在清理垃圾最多的基础上）操作序列最短的前提下，Sleeping Goose 一共有多少种本质不同的清理方案可供选择？

• 第一个问题的答案不取模。
• 第二个问题的答案不取模。
• 第三个问题的答案对 $10^9+7$ 取模。

输入格式

本题有多组数据。

第一行输入一个整数 $T$，表示测试数据的数量。

对于每组测试数据：

$n$ 行，每行两个正整数 $f_i,a_i$：

• $f_i$ 表示 $i$ 号垃圾站的直接上级垃圾站编号，其中 $i \ge 2$，$1 \le f_i \le i-1$。
• $a_i$ 表示 $i$ 号垃圾站中目前堆放的垃圾袋数，其中 $1 \le a_i \le n$。
• 特别地，$f_1=n$（也就是说，第一行输入的两个正整数实际上是 $n$ 和 $a_1$）。

输出格式

对于每组数据，输出一行三个整数，表示题目描述中三个问题的答案：

• 第一个问题的答案不取模。
• 第二个问题的答案不取模。
• 第三个问题的答案对 $10^9+7$ 取模。

样例

2
1 1
2 1
1 1

1 0 1
1 0 1

2
6 6
1 2
1 2
2 3
2 3
2 3
13 10
1 1
2 2
3 3
2 4
3 2
4 3
3 4
4 5
5 3
4 4
5 5
6 6

8 2 3
14 3 1

样例 2 解释

对于第一组数据，最优的 $3$ 种清理方案如下：

• 清理 $4,5,6$ 号垃圾站中的某一个（因此一共有 $3$ 种清理方案），运走 $2$ 袋垃圾，保留 $1$ 袋垃圾，使得 $2$ 号垃圾站堆放的垃圾袋数变为 $4$。
• 清理 $2$ 号垃圾站，运走 $2$ 袋垃圾，保留 $2$ 袋垃圾，使得 $1$ 号垃圾站堆放的垃圾袋数变为 $8$。

这 $3$ 种清理方案对应的操作序列分别是 $\{4,2\},\{5,2\},\{6,2\}$。

请注意，以下 $6$ 种清理方案虽然满足第一个问题的前提，但不满足第二个问题的前提，因此没有计入第三个问题的答案：

• 清理 $4,5,6$ 号垃圾站中的某一个（此处有 $3$ 种选择方案），运走 $2$ 袋垃圾，保留 $1$ 袋垃圾，使得 $2$ 号垃圾站堆放的垃圾袋数变为 $4$。
• 清理 $4,5,6$ 号垃圾站中的另一个（不能是刚刚清理过的那个，此处有 $2$ 种选择方案），运走 $1$ 袋垃圾，保留 $2$ 袋垃圾，使得 $2$ 号垃圾站堆放的垃圾袋数变为 $5$。
• 清理 $2$ 号垃圾站，运走 $2$ 袋垃圾，保留 $3$ 袋垃圾，使得 $1$ 号垃圾站堆放的垃圾袋数变为 $8$。

对于第二组数据，唯一一种最优清理方案对应的操作序列是 $\{12,5,2\}$。

数据范围

对于 $100\%$ 的数据，$1 \le T \le 20$，$1 \le n \le 1000$。

本题共有四个等分的子任务，各子任务的特殊限制如下：

1. 保证 $a_i=1$。
2. 对于 $i \ge 2$ 保证 $f_i=i-1$。
3. 对于 $i \ge 2$ 保证 $f_i=1$。
4. 无特殊限制。