#arc142d. [arc142_d]Deterministic Placing

[arc142_d]Deterministic Placing

给定一棵 NN 个点的树。初始时可以在某些节点上放置一颗棋子,且放置的棋子总数至少为 11,则共有 2N12^N -1 种放置方案。

定义一次操作为,

  • 对于每颗棋子,将其沿着树边移动到与当前节点相邻的一个节点上。

在一次操作内,所有棋子的移动是同时进行的,并且需要遵循以下规则。

  • 每条树边最多被一颗棋子经过。

  • 移动后每个节点上至多有一颗棋子。

现在你需要统计 2N12^N-1 种放置方案中,满足以下条件的方案数,对 998244353998244353 取模。

  • 对于每个非负整数 KK,满足以下条件。
    • 至少能进行 KK 次操作。
    • 无论如何进行这 KK 次操作,最终所有棋子占据的节点集合唯一。

2N2×1052 \le N \le 2 \times 10^5