/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
|A_i - A_{i+1}| \geq K (1 \le i \le N - 1)
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 1000
- 1 \leq M \leq 5000
- 0 \leq K \leq M-1
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 1
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,2)
- (1,3)
- (2,1)
- (2,3)
- (3,1)
- (3,2)
入力例 2
3 3 2
出力例 2
2
条件を満たす数列は以下の 2 つです。
- (1,3,1)
- (3,1,3)
入力例 3
100 1000 500
出力例 3
657064711
答えを 998244353 で割った余りを出力してください。
Score : 500 points
Problem Statement
How many integer sequences A=(A_1,\ldots,A_N) of length N satisfy all the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
|A_i - A_{i+1}| \geq K (1 \le i \le N - 1)
Since the count can be enormous, find it modulo 998244353.
Constraints
- 2 \leq N \leq 1000
- 1 \leq M \leq 5000
- 0 \leq K \leq M-1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the count modulo 998244353.
Sample Input 1
2 3 1
Sample Output 1
6
The following 6 sequences satisfy the conditions.
- (1,2)
- (1,3)
- (2,1)
- (2,3)
- (3,1)
- (3,2)
Sample Input 2
3 3 2
Sample Output 2
2
The following 2 sequences satisfy the conditions.
- (1,3,1)
- (3,1,3)
Sample Input 3
100 1000 500
Sample Output 3
657064711
Print the count modulo 998244353.