Heiltöluruna $V_1, V_2, \dots, V_N$ kallast ofurminnkandi ef $V_N \ge 0$, og $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ fyrir öll $1 \le i < N$.
Gefnar eru jákvæðar heiltölur $N$ og $M$. Finndu fjölda para af heiltölurunum $A$ og $B$ af lengd $N$ þannig að $1 \le A_i, B_i \le M$ fyrir öll $1 \le i \le N$, og fyrir allar ofurminnkandi runur $V$ af lengd $N$ gildir:
$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$
Þar sem fjöldi slíkra para getur verið mjög mikill skaltu prenta svarið módulo $998\,244\,353$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
T N M :
- Öll inntaksgildi eru heiltölur.
- $1 \le T \le 100$
- $1 \le N, M \le 5000$
- Tryggt er að summa $N$ yfir öll prófunartilvik fari ekki yfir $5000$.
- Tryggt er að summa $M$ yfir öll prófunartilvik fari ekki yfir $5000$.
Úttak
Fyrir hvert prófunartilvik skaltu prenta eina heiltölu — fjölda para af runum $(A, B)$ sem uppfylla skilyrðin, módulo $998\,244\,353$.
Dæmi
Dæmi um inntak 1
4 1 1 2 2 2 1 34 43
Dæmi um úttak 1
1 10 1 711021868
Athugasemd
Prófunartilvik 1: Eina mögulega parið af runum er $([1], [1])$, og það er gilt.
Prófunartilvik 2: Eftirfarandi eru gild pör af runum:
- Fyrir $B = [1, 1]$ er hvaða val sem er á $A$ gilt. Það eru $4$ mögulegir valkostir.
- Fyrir $B = [1, 2]$ eru gildir valkostir á $A$ þeir $[1, 2], [2, 1], [2, 2]$.
- Fyrir $B = [2, 1]$ eru gildir valkostir á $A$ þeir $[2, 1], [2, 2]$.
- Fyrir $B = [2, 2]$ er eini gildi valkosturinn á $A$ sá $[2, 2]$.
Þannig að fjöldi gildra para af runum jafngildir $4 + 3 + 2 + 1 = 10$.