시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 90 | 24 | 17 | 27.869% |
You have a set A of non-negative integers that is a union of n ranges [li; ri]. How many 4-element subsets with sum equal to s does A contain? Output this number modulo 998 244 353.
The first line of the input contains two integers n and s (1 ≤ n ≤ 400; 0 ≤ s ≤ 8 · 108), denoting the number of ranges and the required sum.
Each of the following n lines contains two integers li and ri (0 ≤ li ≤ ri ≤ 2·108; ri < li+1), denoting the boundaries of the i-th range.
Display the number of 4-element subsets of A with sum equal to s, modulo 998 244 353.
2 17 1 3 5 8
4
In the example test case, A = {1, 2, 3, 5, 6, 7, 8}. Its 4-element subsets with sum equal to 17 are {1, 2, 6, 8}, {1, 3, 5, 8}, {1, 3, 6, 7}, and {2, 3, 5, 7}.