تُسمى متتالية الأعداد الصحيحة $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$.