题目描述

题目译自 PA 2021 Runda 5 Zbiory niezależne

树 $T=(V, E)$ 是一个无向连通且无环的简单图。在本题中，我们考虑 $c$ 色树，即树上每个节点是 $c$ 种颜色之一的树。

两棵有色树 $T_1=(V_1,E_1),T_2=(V_2,E_2)$ 相等，如果满足：

• 存在双射 $\pi:V_1\to V_2$，满足对于任意节点对 $u,v\in V_1$，存在关系 $\{u,v\}\in E_1$ 当且仅当 $\{\pi(u),\pi(v)\}\in E_2$，且；
• 对于任意节点 $v\in V_1$，$T_1$ 中 $v$ 节点的颜色和 $T_2$ 中 $\pi(v)$ 节点的颜色相同。

我们称一棵树 $T=(V,E)$ 的一个独立集为任意节点的子集 $S\subseteq V$，满足 $S$ 中没有两不同节点被一条边相连。独立集 $S$ 的大小等于属于 $S$ 集合的节点个数。

给定三个整数 $l,r,c$，求问有多少不同的 $c$ 色树满足其最大独立集的大小至少为 $l$，至多为 $r$？由于结果可能会非常大，所以请求出它对 $998\ 244\ 353$ 取模后的结果。

输入格式

第一行包含三个整数 $l,r,c\ (1\le l\le r\le 5\times 10^5,1\le c\le 998\ 244\ 352)$。

输出格式

输出一行一个整数，表示满足最大独立集大小至少为 $l$ 至多为 $r$ 的不同 $c$ 色树数量对 $998\ 244\ 353$ 取模后的值。

1 3 1

9

1 3 2

149

数据范围与提示

对于一些子任务，满足 $l=r$，对于一些（可能是其他的）子任务，满足 $c=1$。