题目描述

AtCoder 语有 $L$ 种不同的字符。由 AtCoder 语的字符组成的 $N$ 个字符的字符串 $s$，满足以下条件的有多少种？请输出答案对 $998244353$ 取模后的结果。

• 字符串 $s$ 的任意一个“$K$ 个字符的子序列”都是不同的。严格来说，从字符串 $s$ 中选出 $K$ 个字符，按照原有顺序连接，得到 $K$ 个字符的字符串的方法有 $_N\mathrm{C}_K$ 种，这些方法得到的所有字符串都互不相同。

$_N\mathrm{C}_K$ 表示从 $N$ 个元素中选出 $K$ 个的方法总数。更严格地说，$_N\mathrm{C}_K$ 等于 $N!$ 除以 $K! \times (N-K)!$。

输入格式

输入以以下格式从标准输入读入。

$N$ $K$ $L$

输出格式

请输出答案。

样例 1

输入

4 3 2

输出

2

样例 2

输入

100 80 26

输出

496798269

样例 3

输入

100 1 26

输出

0

样例 4

输入

500000 172172 503746693

输出

869120

说明/提示

限制条件

• $1 \leq K < N \leq 500000$
• $1 \leq L \leq 10^9$
• 输入均为整数

样例解释 1

将 AtCoder 语的第 $1$ 种字符记为 a，第 $2$ 种字符记为 b，满足条件的字符串有 abab、baba 共 $2$ 种。

样例解释 2

满足条件的字符串大约有 $10^{86}$ 种，这里输出对 $998244353$ 取模后的 $496798269$。

由 ChatGPT 4.1 翻译