Four Elements
시간 제한2초메모리 제한512 MB
정수 구간 n개의 합집합에서 원소 4개의 합이 s인 부분집합의 개수를 998244353으로 나눈 나머지로 구한다.
문제
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.
힌트
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}.