P9042 [PA 2021] Independent Sets

A tree $T = (V, E)$ is a simple undirected connected graph with no cycles. In this problem, we consider $c$-colored trees, i.e., trees in which each node has one of $c$ colors. Two colored trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ are equal if and only if: - There exists a bijection $\pi : V_1 \to V_2$ such that for any pair of nodes $(u, v) \in V_1$, $\{u,v\} \in E_1$ if and only if $\{\pi(u), \pi(v)\} \in E_2$. - For any node $v \in V_1$, the color of node $v$ in $T_1$ is the same as the color of node $\pi(v)$ in $T_2$. We call an independent set of a tree $T = (V, E)$ any subset of nodes $S \subseteq V$ such that no two different nodes in $S$ are connected by an edge. The size of an independent set $S$ is the number of nodes in $S$. Given three integers $l$, $r$, and $c$, find how many different $c$-colored trees have a maximum independent set size in $[l, r]$. Since the answer may be very large, output it modulo $998244353$.

One line with three integers $l$, $r$, and $c$.

One line with one integer, the required value.

For $100\%$ of the testdata, $1 \leq l \leq r \leq 5 \times 10^5$ and $1 \leq c \leq 998244352$. Translated by ChatGPT 5