你有一个由 $n$ 个区间 $[l_i, r_i]$ 的并集构成的非负整数集合 $A$。集合 $A$ 中有多少个 4 元子集，其元素之和等于 $s$？请输出该数量对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含两个整数 $n$ 和 $s$ ($1 \le n \le 400$; $0 \le s \le 8 \cdot 10^8$)，分别表示区间的数量和目标和。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($0 \le l_i \le r_i \le 2 \cdot 10^8$; $r_i < l_{i+1}$)，表示第 $i$ 个区间的边界。

输出格式

输出集合 $A$ 中和为 $s$ 的 4 元子集的数量，对 $998\,244\,353$ 取模。

样例

输入 1

2 17
1 3
5 8

输出 1

4

说明

在样例测试中，$A = \{1, 2, 3, 5, 6, 7, 8\}$。其和为 $17$ 的 4 元子集有 $\{1, 2, 6, 8\}$、$\{1, 3, 5, 8\}$、$\{1, 3, 6, 7\}$ 和 $\{2, 3, 5, 7\}$。