#P18482. Hierarchies of Judges
Hierarchies of Judges
Hierarchies of Judges
树之国正在进行司法改革,政府需要选出一套新的司法层级。层级由 位法官组成,法官用 到 的整数编号。
司法层级是一棵有根的、顶点带有编号的树,顶点代表法官。每位法官都有一份有序的直属下级列表,也就是它在有根树中的孩子列表。此外,每位法官要么可靠,要么不可靠。
如果对于每位法官,在他本人及其所有直属下级之中,可靠者至少占一半,就称这个司法层级公平。恰好一半也满足条件。
如果满足以下三个条件中的至少一个,就认为两套司法层级不同:
- 某位法官在其中一套层级中可靠,而在另一套层级中不可靠。
- 某位法官在两套层级中的直属下级集合不同。
- 某位法官的不可靠直属下级之间的相对顺序在两套层级中不同。
也就是说,只有不可靠孩子彼此之间的相对顺序参与区分;可靠孩子彼此的排列,以及可靠孩子与不可靠孩子之间的交错位置,都不会单独使两套层级不同。下方原图有助于理解这个等价关系。
政府想遍历所有不同的公平司法层级,以此选出新层级。请计算可选层级数量对 取模的结果。
输入格式
输入一行,一个整数 (),表示法官数量。
输出格式
输出一个整数,表示由 位法官构成的不同公平司法层级数量对 取模的结果。
原样例 1
1
1
原样例 2
3
24
原样例 3
5
3190
原样例 4
100
413875584
原图说明
每位法官的直属下级画在他的下方,从左到右对应给出的下级列表。灰色代表可靠,白色代表不可靠。
下图上方的两个公平层级被视为相同;下方的四个层级两两不同。
