$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$ шарты орындалса.
Оң бүтін $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-мысал кіріс
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$-ға тең.