树 $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$ 中包含的顶点数。

给定三个整数 $\ell, r$ 和 $c$。求有多少种不同的 $c$-着色树，其最大独立集的大小至少为 $\ell$ 且至多为 $r$？由于结果可能非常大，请输出其对 $998\,244\,353$ 取模后的余数。

输入格式

输入的第一行包含三个整数 $\ell, r, c$ ($1 \le \ell \le r \le 500\,000, 1 \le c \le 998\,244\,352$)。

输出格式

输出一行一个整数：所有满足最大独立集大小在区间 $[\ell, r]$ 内的 $c$-着色树的数量对 $998\,244\,353$ 取模后的结果。

样例

样例输入 1

1 3 1

样例输出 1

9

样例输入 2

1 3 2

样例输出 2

149

说明

第一个样例的解释：所有最大独立集大小为 1、2 或 3 的不同 1-着色树如下所示：

子任务

在某些测试组中，满足条件 $\ell = r$。此外，在某些（可能不同的）测试组中，满足条件 $c = 1$。