18480번 - Four Elements 다국어

문제

You have a set A of non-negative integers that is a union of n ranges [l_i; r_i]. 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 · 10⁸), denoting the number of ranges and the required sum.

Each of the following n lines contains two integers l_i and r_i (0 ≤ l_i ≤ r_i ≤ 2·10⁸; r_i < l_i+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.

제한

힌트

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}.