整数列 $V_1, V_2, \dots, V_N$ は、$V_N \ge 0$ であり、かつすべての $1 \le i < N$ に対して $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ を満たすとき、超減少(super decreasing)であると呼ばれます。
正の整数 $N$ と $M$ が与えられます。長さ $N$ の整数列 $A$ と $B$ の組であって、すべての $1 \le i \le N$ に対して $1 \le A_i, B_i \le M$ を満たし、さらに長さ $N$ のすべての超減少数列 $V$ に対して
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
が成り立つものの個数を求めてください。このような組の個数は非常に大きくなる可能性があるため、答えを $998\,244\,353$ で割った余りを出力してください。
入力
入力は以下の形式で与えられます:
T N M :
- 入力される値はすべて整数である。
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- すべてのテストケースにおける $N$ の総和は $5000$ を超えないことが保証される。
- すべてのテストケースにおける $M$ の総和は $5000$ を超えないことが保証される。
出力
各テストケースについて、条件を満たす数列の組 $(A, B)$ の個数を $998\,244\,353$ で割った余りを表す整数を 1 つ出力してください。
入出力例
入力例 1
4 1 1 2 2 2 1 34 43
出力例 1
1 10 1 711021868
注記
テストケース 1: あり得る唯一の数列の組は $([1], [1])$ であり、これは条件を満たします。
テストケース 2: 条件を満たす数列の組は以下の通りです:
- $B = [1, 1]$ のとき、$A$ はどのように選んでも条件を満たします。選び方は $4$ 通りあります。
- $B = [1, 2]$ のとき、条件を満たす $A$ の選び方は $[1, 2], [2, 1], [2, 2]$ です。
- $B = [2, 1]$ のとき、条件を満たす $A$ の選び方は $[2, 1], [2, 2]$ です。
- $B = [2, 2]$ のとき、条件を満たす唯一の $A$ の選び方は $[2, 2]$ です。
したがって、条件を満たす数列の組の個数は $4 + 3 + 2 + 1 = 10$ です。