Codeforces Round 738 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

fft

math

number theory

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Mocha and Stars

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMocha 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$$$.

Input

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.

Output

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

Examples

Input

2 4 1 3 1 2

Output

4

Input

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

Output

251

Input

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

Output

47464146

Note

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$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/27/2024 19:49:05 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|