← 返回题目列表

Codeforces · 1559/E

E. 摩卡和星星

中文机器翻译题面 查看原题

摩卡想成为一名占星家。枝江市有$$$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$$$。