7820: ABC253 —— E - Distance Sequence
[Creator : ]
Description
How many integer sequences $A=(A_1,…,A_N)$ of length $N$ satisfy all the conditions below?
-
$1≤A_i≤M\ (1≤i≤N)$
-
$∣A_i−A_{i+1}∣≥K\ (1≤i≤N−1)$
Input
Input is given from Standard Input in the following format:
$N\ M\ K$
$N\ M\ K$
Output
Print the count modulo 998244353.
Constraints
$2≤N≤1000$
$1≤M≤5000$
$0≤K≤M−1$
All values in input are integers.
$1≤M≤5000$
$0≤K≤M−1$
All values in input are integers.
Sample 1 Input
2 3 1
Sample 1 Output
6
The following 6 sequences satisfy the conditions.
- (1,2)
- (1,3)
- (2,1)
- (2,3)
- (3,1)
- (3,2)
Sample 2 Input
3 3 2
Sample 2 Output
2
The following 2 sequences satisfy the conditions.
- (1,3,1)
- (3,1,3)
Sample 3 Input
100 1000 500
Sample 3 Output
657064711