Four Elements

Time limit2sMemory limit512 MB

Summary

Count the 4-element subsets of a union of n disjoint integer ranges whose sum equals s, modulo 998244353.

Level: Hard9 of 10
Topics: Math, Combinatorics, Intervals, Dynamic programming
Solved: No attempts yet

Problem

Set $A$ is the union of $n$ ranges $[l_i, r_i]$ . How many 4-element subsets of $A$ have a sum equal to $s$ ? Print the count modulo 998 244 353.

Input

The first line contains two integers $n$ and $s$ ( $1 \le n \le 400$ , $0 \le s \le 8 \cdot 10^8$ ). Each of the next $n$ lines contains two integers $l_i$ and $r_i$ , the bounds of the $i$ -th range ( $0 \le l_i \le r_i \le 2 \cdot 10^8$ , $r_i < l_{i+1}$ ).

Output

Print the number of 4-element subsets of $A$ with sum $s$ , modulo 998 244 353.

Hint

In the example, $A = \{1, 2, 3, 5, 6, 7, 8\}$ . The 4-element subsets with sum 17 are $\{1, 2, 6, 8\}$ , $\{1, 3, 5, 8\}$ , $\{1, 3, 6, 7\}$ , and $\{2, 3, 5, 7\}$ .

Examples1

Example 1
Input
```
2 17
1 3
5 8
```
Expected output
```
4
```