Ashley 正在为 Brandon's Online Judge 上的另一场编程竞赛进行训练。

Ashley 距离下一次编程竞赛还有 $k$ 周的训练时间。她的教练 Tom 非常忙，不再为 Ashley 精心挑选特定的训练题目。每周开始时，Tom 都会从 Brandon's Online Judge 的 $n$ 道题库中独立且均匀地随机抽取 $p$ 道不同的题目分配给 Ashley。Tom 以这种方式总共生成了 $k$ 组题目。

Ashley 会认真完成 Tom 挑选出的每一道题。然而，如果存在任意两个不同的周，它们包含至少一道相同的题目，她就会感到烦恼，因为她希望解决的题目都是唯一的。

计算 Ashley 感到烦恼的概率。

输入格式

输入的第一行也是唯一一行包含三个整数 $n$ ($1 \le n \le 10^7$)，$k$ ($1 \le k \le 10^7$) 和 $p$ ($1 \le p \le n$)。

输出格式

设 $p$ 为 Ashley 感到烦恼的概率。可以证明 $p$ 可以写成有理数 $\frac{x}{y}$，其中 $\gcd(x, y) = 1$ 且 $y \not\equiv 0 \pmod{998244353}$。定义 $r$ 为 $[0, 998244353)$ 中唯一的整数，满足 $r \cdot y \equiv x \pmod{998244353}$。输出 $r$。

可以证明，在给定的约束条件下，$r$ 必然存在且唯一。

说明

在第一个样例中，可以证明 Ashley 感到烦恼的概率是 $\frac{7}{9}$。注意 $110916040 \cdot 9 \equiv 7 \pmod{998244353}$，因此该测试用例的输出为 $110916040$。

在第二个样例中，可以证明 Ashley 总是会感到烦恼。注意 $1 \cdot 1 \equiv 1 \pmod{998244353}$，因此该测试用例的输出为 $1$。

在第三个样例中，可以证明 Ashley 永远不会感到烦恼。注意 $0 \cdot 1 \equiv 0 \pmod{998244353}$，因此该测试用例的输出为 $0$。

样例

样例输入 1

3 3 1

样例输出 1

110916040

样例输入 2

3 2 2

样例输出 2

1

样例输入 3

3 1 1

样例输出 3

0