题目描述

对于一棵包含 $n$ 个节点的无根树 $T$，我们这样定义函数 $f(T)$： $\hspace{23pt}\bullet\,$有一个足够宽且足够高的水缸，其中装有高度为正整数 $h$ 的染料。初始时，树上所有节点均未被染色。一次操作中，你需要选择一个节点 $r$ 作为根，将树从根节点提起并浸入染料中，树的最下方 $h$ 层节点会被染色；已经被染色的节点不会恢复为未染色。 $\hspace{23pt}\bullet\,$具体地，以节点 $r$ 为根时，令 $\operatorname{dist}_r(u)$ 表示节点 $u$ 到节点 $r$ 的距离$^\texttt{[1]}$，并令 $m_r=\max\limits_{1\leq u\leq n}\operatorname{dist}_r(u)$ 表示树高。此次操作会染色所有满足 $m_r-\operatorname{dist}_r(u)<h$ 的节点 $u$。 $\hspace{23pt}\bullet\,$对于每个 $1\leq k\leq n$，令 $h_k$ 表示恰好进行 $k$ 次操作后能使所有节点均被染色时，$h$ 的最小值。每次操作均可重新选择根节点。 $\hspace{23pt}\bullet\,$定义 $\displaystyle f(T)=\bigoplus\limits_{i=1}^{n}h_i$，即 $h_1,h_2,\dots,h_n$ 的异或和$^\texttt{[2]}$。 请你求出节点数为 $n$ 的所有有标号无根树 $T$ 的 $\operatorname{f}(T)$ 之和对 $998\,244\,353$ 取模的结果。 【名词解释】 树上距离$^\texttt{[1]}$：从节点 $u$ 到节点 $v$ 的简单路径上边的数量。 异或和$^\texttt{[2]}$：对于若干个数 $a_1,a_2,\dots,a_n$，它的异或和为 $a_1 \operatorname{xor} a_2 \operatorname{xor}\dots \operatorname{xor} a_n$$^\texttt{[3]}$。特殊的，空集合的异或和为 $0$。 $\operatorname{xor}^\texttt{[3]}$：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。官方中文

输入格式

输入一个整数 $n\left(1\leq n\leq500\right)$，表示树的节点数。官方中文

输出格式

输出一个整数，表示答案对 $998\,244\,353$ 取模的结果。官方中文