Background

This problem is suspected to be wrong. Under the current Constraints, it is known that there is no solution with time complexity lower than $O(N^2\log N)$, let alone a solution that can pass this problem. If Lanqiao Cup adds extra Constraints after the contest, this problem will be adjusted accordingly.

Problem Description

Xiaolan’s school is organizing the annual sports meet. There are $N$ classes participating in this sports meet, and the $i$-th class has registered $a_i$ students.

To ensure fairness and attractiveness of the competition, the organizing committee decides to select $M$ students from all registered students to officially participate. At the same time, to avoid one class having too many participants, the committee sets the rule that the number of selected participants from the same class cannot exceed $K$.

Now, please help Xiaolan compute how many different ways there are to select the participating students. Two selection plans are considered different if and only if at least one selected student is different. Since the number of plans may be very large, output the result modulo $998244353$.

Input Format

The first line contains three positive integers $N, M, K$, representing the number of classes, the total number of students to select, and the maximum number of selected students allowed from each class.

The second line contains $N$ positive integers $a_1, a_2, \dots, a_N$, representing the number of registered students in each class.

Output Format

Output one line with one integer, representing the number of valid selection plans modulo $998244353$.

3 4 2
2 3 2

31

Hint

Sample Explanation

The three classes register $2, 3, 2$ students respectively, for a total of $7$ students. If there were no limit of at most $2$ students per class, choosing $4$ students from $7$ would give $\binom{7}{4} = 35$ plans.

The only invalid case is when all $3$ students from class $2$ are selected. Then we still need to choose $1$ student from the $4$ students in classes $1$ and $3$, which gives $4$ invalid plans.

Therefore, the number of valid plans is $35 - 4 = 31$.

Testdata Scale and Conventions

For $30\%$ of the test cases, $1 \le N, M, K, a_i \le 20$.

For $80\%$ of the test cases, $1 \le N, M, K, a_i \le 500$.

For all test cases, $1 \le N, M, K, a_i \le 50000$, and $M \le \sum_{i=1}^N a_i$.

Translated by ChatGPT 5