摩卡想成为一名占星家。枝江市有$$$n$$$颗星星,第$$$i$$$颗星星的亮度为$$$a_i$$$。
Mocha 认为这些 $$$n$$$ 恒星形成了一个星座,她使用 $$$(a_1,a_2,\ldots,a_n)$$$ 来显示其状态。如果满足以下所有三个条件,则称为数学状态:
- 对于所有 $$$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$$$ 求模。
如果存在 $$$i$$$ ($$$1\le i\le n$$$) 使得 $$$a_i \ne b_i$$$ 存在,则两个状态 $$$(a_1,a_2,\ldots,a_n)$$$ 和 $$$(b_1,b_2,\ldots,b_n)$$$ 被视为不同。
输入
第一行包含两个整数 $$$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$$$ 颗恒星的亮度范围。
输出
打印一个整数 - 该星座的不同数学状态的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2 4 1 3 1 2
输出 #1
4
输入 #2
5 10 1 10 1 10 1 10 1 10 1 10
输出 #2
251
输入 #3
5 100 1 94 1 96 1 91 4 96 6 97
输出 #3
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$$$。