Mocha 与星星

Mocha 想成为一名占星师。在之江可以看到 $n$ 颗星星，第 $i$ 颗星星的亮度为 $a_i$。

Mocha 认为这 $n$ 颗星星构成了一个星座，她用 $(a_1, a_2, \dots, a_n)$ 来表示其状态。一个状态被称为数学状态，如果满足以下三个条件：

• 对于所有 $i$（$1 \le i \le n$），$a_i$ 是 $[l_i, r_i]$ 范围内的整数。
• $\sum_{i=1}^n a_i \le m$。
• $\gcd(a_1, a_2, \dots, a_n) = 1$。

其中 $\gcd(a_1, a_2, \dots, a_n)$ 表示整数 $a_1, a_2, \dots, a_n$ 的最大公约数。

Mocha 想知道这个星座有多少个不同的数学状态。由于答案可能很大，你需要输出它对 $998244353$ 取模的结果。

两个状态 $(a_1, a_2, \dots, a_n)$ 和 $(b_1, b_2, \dots, b_n)$ 被认为是不同的，如果存在某个 $i$（$1 \le i \le n$）使得 $a_i \neq b_i$。

输入
第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 50$，$1 \le m \le 10^5$）——星星的数量和亮度总和的上界。
接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le m$）——第 $i$ 颗星星的亮度范围。

输出
输出一个整数——不同数学状态的数量，对 $998244353$ 取模。

样例

样例 1

输入

2 4
1 3
1 2

输出

4

样例 2

输入

5 10
1 10
1 10
1 10
1 10
1 10

输出

251

样例 3

输入

5 100
1 94
1 96
1 91
4 96
6 97

输出

47464146

注意

在第一个样例中，有 $4$ 个不同的数学状态：

• $a_1=1, a_2=1$。
• $a_1=1, a_2=2$。
• $a_1=2, a_2=1$。
• $a_1=3, a_2=1$。