시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

2 17
1 3
5 8

예제 출력 1

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