Sebuah barisan bilangan bulat $V_1, V_2, \dots, V_N$ disebut super menurun (super decreasing) jika $V_N \ge 0$, dan $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ untuk semua $1 \le i < N$.
Diberikan bilangan bulat positif $N$ dan $M$, carilah banyaknya pasangan barisan bilangan bulat $A$ dan $B$ dengan panjang $N$ sedemikian sehingga $1 \le A_i, B_i \le M$ untuk semua $1 \le i \le N$, dan untuk semua barisan super menurun $V$ dengan panjang $N$, berlaku:
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Karena banyaknya pasangan tersebut bisa sangat besar, cetak jawabannya modulo $998\,244\,353$.
Masukan
Masukan diberikan dalam format berikut:
T N M :
- Semua nilai masukan adalah bilangan bulat.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Dijamin bahwa jumlah $N$ di seluruh kasus uji tidak melebihi $5000$.
- Dijamin bahwa jumlah $M$ di seluruh kasus uji tidak melebihi $5000$.
Keluaran
Untuk setiap kasus uji, keluarkan satu bilangan bulat — banyaknya pasangan barisan $(A, B)$ yang memenuhi kondisi, modulo $998\,244\,353$.
Contoh
Contoh Masukan 1
4 1 1 2 2 2 1 34 43
Contoh Keluaran 1
1 10 1 711021868
Catatan
Kasus uji 1: Satu-satunya pasangan barisan yang mungkin adalah $([1], [1])$, dan pasangan ini valid.
Kasus uji 2: Berikut adalah pasangan-pasangan barisan yang valid:
- Untuk $B = [1, 1]$, pilihan $A$ mana pun valid. Terdapat $4$ pilihan yang mungkin.
- Untuk $B = [1, 2]$, pilihan $A$ yang valid adalah $[1, 2], [2, 1], [2, 2]$.
- Untuk $B = [2, 1]$, pilihan $A$ yang valid adalah $[2, 1], [2, 2]$.
- Untuk $B = [2, 2]$, satu-satunya pilihan $A$ yang valid adalah $[2, 2]$.
Jadi, banyaknya pasangan barisan yang valid sama dengan $4 + 3 + 2 + 1 = 10$.