You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

每到春节前夕，便是我们BCOI oier的狂欢，孩子们对春节白蛋进行染色，使其五颜六色，但是我们也有染色规则

题目描述

我们从 $m$ 种颜色中选择最多 $k$ 种颜色给一行 $n$ 个小球染色, 要求相邻两个小球的颜色不同, 一共有多少染色方案(注意同样的染色不同选色是不同方案)?

输入格式

第一行输入三个整数 $n, m, k$

输出格式

输出 $1$ 个整数，表示所求的答案。答案可能很大, 需要对 998244353 取模

样例 #1

样例输入 #1

2 5 1

样例输出 #1

0

样例 #2

样例输入 #2

1 2 2

样例输出 #2

2

数据范围

• $50\%$ 的数据 $1 \le k \le m \le 10^3, 1 \le n \le 10^6$
• $100\%$ 的数据 $1 \le k \le m \le 10^6, 1 \le n \le 10^9$