站外题求助

Problem D 区间(1s,512MB)

Description

有 n 个容器排成一列，每个容器的容量上限为 t。你现在指挥着 m 个人， 对每个人你需要指定一段非空的容器区间，让他往这段区间里面的每个容器倒 1 单位的水，但是必须保证每个容器里面的水不能溢出（不能超出容量上限）。

请问一共有多少种合法的倒水方式，答案对 998244353 取模。

Input 第一行三个正整数 n,m,t。

Output 一行一个整数，表示答案对 998244353 取模后的值。

Sample Input 1

3 2 1

Sample Output 1

10

Sample Input 2

10 10 5

Sample Output 2

422290533

Constraints

对于前 20%的数据，n,m,t≤4

对于前 60%的数据，n,m,t≤40

另有 10%的数据满足：t=1

另有 10%的数据满足：t=m

对于 100%的数据，满足 n,m,t≤100，t≤m