Цілочисельна послідовність $V_1, V_2, \dots, V_N$ називається надспадною, якщо $V_N \ge 0$ та $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ для всіх $1 \le i < N$.
Дано додатні цілі числа $N$ і $M$. Знайдіть кількість пар цілочисельних послідовностей $A$ та $B$ довжини $N$, таких що $1 \le A_i, B_i \le M$ для всіх $1 \le i \le N$, і для всіх надспадних послідовностей $V$ довжини $N$ виконується:
$$\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$.