题目内容

在一款游戏中，有 $n$ 个技能，编号为 $1$ 到 $n$。初始时，技能 $1$ 已经学习过。其他每个技能均有一个直接前置技能，学会前置技能后才有资格学习该技能。这些前置关系构成一个以技能 $1$ 为根的树形结构，即除 $1$ 外每个技能恰好有一个前置技能，且从 $1$ 出发可以到达所有技能。

每天玩家可以选择一个已经学会但尚未学习过的技能进行学习（初始时，技能 $1$ 的直接后继技能处于已学会未学习状态）。学习该技能后，所有以它为直接前置的技能变为“已学会”状态可供后续学习。经过 $n-1$ 天后，所有 $n$ 个技能都被学习过。

一个学习顺序是一个长度为 $n-1$ 的序列，记录每天学习的技能编号。请你计算不同的合法学习顺序总数。由于答案可能很大，请输出其对 $10^9+7$ 取模后的结果。

数据范围：技能总数 $n$ 满足 $1 \le n \le 2\times 10^5$。测试用例数 $T$ 满足 $1 \le T \le 10$。所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输入描述