#P17624. [qaswed12 OI R1] BrrTree
[qaswed12 OI R1] BrrTree
背景
Brr Brr patapim 是一只意大利山海经动物。
题目描述
我们定义一颗 brr 树为叶节点数严格大于总节点数二分之一且以 为根的有标号树。
给定 组数据,每组数据给定一个整数 。
请你求出本质不同的,有 个节点的 brr 树的数量,答案对 取模。
两棵 brr 树本质不同当且仅当,存在点 和点 在恰好其中一棵 brr 树中有连边。
某个点为叶子节点当且仅当其没有儿子节点。
输入格式
第一行一个整数 表示询问组数。
接下来 行,每行一个正整数 。
输出格式
共 行,每行一个整数表示答案。
6
2
3
5
11
1145
14587
0
1
29
239726411
165996705
197549689
提示
样例解释
当 时显然无解。
当 时, 均为 的儿子结点显然为一组解。
当 时,对于形态如下的树,各有 种:




其中 是 的一个排列。
于是答案为 种。
注意本题要求本质不同的树,即如下两棵树算作相同:


数据范围与约定
本题开启捆绑测试,请注意本题特殊的时间限制。
| 子任务编号 | 分值 | |
|---|---|---|
对于 的数据,满足 ,