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.

题目描述

求有多少个长度为 $n$ 的序列 $A = (A_1 , . . . A_n )$ 满足如下条件： $1 ≤ A_i ≤ m$ 。 $|A_i − A_{i+1} | ≥ k(1 ≤ i ≤ n − 1)。$ $请输出答案模 998244353 的余数。$

输入格式

$一行三个整数 n, m, k 。$

输出格式

$一行一个整数，为答案模 998244353 的余数。$

样例1输入

2 3 1

样例1输出

6

样例2输入

100 1000 500

样例2输出

657064711

数据范围

$对于 10\% 的数据 ，保证 n = 2 。$

$对于另外 10\% 的数据 ，保证 k = 0 。$

$对于另外 10\% 的数据 ，保证 k = m − 1 。$

$对于另外 10\% 的数据 ，保证 m = 1 。$

$对于另外 20\% 的数据 ，保证 2 ≤ n ≤ 10, 1 ≤ m ≤ 3, 0 ≤ k ≤ m − 1 。 $

$对于另外 30\% 的数据，保证 2 ≤ n ≤ 40, 1 ≤ m ≤ 100, 0 ≤ k ≤ m − 1 。 $

$对于 100\% 的数据，保证 2 ≤ n ≤ 1000, 1 ≤ m ≤ 5000, 0 ≤ k ≤ m − 1 。 $