CF1559E.Mocha and Stars

Mocha wants to be an astrologer. There are $n$ stars which can be seen in Zhijiang, and the brightness of the $i$-th star is $a_i$.

Mocha considers that these $n$ stars form a constellation, and she uses $(a_1,a_2,\ldots,a_n)$ to show its state. A state is called mathematical if all of the following three conditions are satisfied:

• For all $i$ ($1\le i\le n$), $a_i$ is an integer in the range $[l_i, r_i]$.
• $\sum \limits _{i=1} ^ n a_i \le m$.
• $\gcd(a_1,a_2,\ldots,a_n)=1$.

Here, $\gcd(a_1,a_2,\ldots,a_n)$ denotes the greatest common divisor (GCD) of integers $a_1,a_2,\ldots,a_n$.

Mocha is wondering how many different mathematical states of this constellation exist. Because the answer may be large, you must find it modulo $998\,244\,353$.

Two states $(a_1,a_2,\ldots,a_n)$ and $(b_1,b_2,\ldots,b_n)$ are considered different if there exists $i$ ($1\le i\le n$) such that $a_i \ne b_i$.

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

Mocha 认为这 $n$ 颗星星构成了一组星座，她用 $(a_1,a_2,\ldots,a_n)$ 表示其状态。若一个状态满足以下三个条件，则称其为数学的（mathematical）：

• 对所有 $i$（$1\le i\le n$），$a_i$ 是区间 $[l_i, r_i]$ 内的一个整数；
• $\sum \limits _{i=1} ^ n a_i \le m$；
• $\gcd(a_1,a_2,\ldots,a_n)=1$。

其中，$\gcd(a_1,a_2,\ldots,a_n)$ 表示整数 $a_1,a_2,\ldots,a_n$ 的最大公约数（GCD）。

Mocha 想知道该星座共有多少种不同的数学状态。由于答案可能很大，你必须输出其对 $998\,244\,353$ 取模的结果。

两个状态 $(a_1,a_2,\ldots,a_n)$ 和 $(b_1,b_2,\ldots,b_n)$ 被视为不同，当且仅当存在某个 $i$（$1\le i\le n$）使得 $a_i \ne b_i$。

The first line contains two integers $n$ and $m$ ($2 \le n \le 50$, $1 \le m \le 10^5$) — the number of stars and the upper bound of the sum of the brightness of stars.

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le m$) — the range of the brightness of the $i$-th star.

第一行包含两个整数 $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$ 颗星星亮度的取值范围。

Print a single integer — the number of different mathematical states of this constellation, modulo $998\,244\,353$.

输出一个整数——该星座的不同数学状态的数量，对 $998\,244\,353$ 取模。

In the first example, there are $4$ different mathematical states of this constellation:

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

在第一个例子中，该构型共有 $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$。