[Solution] Mocha and Stars solution codeforces

Mocha and Stars solution codeforces


Mocha wants to be an astrologer. There are nn stars which can be seen in Zhijiang, and the brightness of the ii-th star is aiai.

Mocha considers that these nn stars form a constellation, and she uses (a1,a2,,an)(a1,a2,…,an) to show its state. A state is called mathematical if all of the following three conditions are satisfied:

  • For all ii (1in1≤i≤n), aiai is an integer in the range [li,ri][li,ri].
  • i=1naim∑i=1nai≤m.
  • gcd(a1,a2,,an)=1gcd(a1,a2,…,an)=1.

Here, gcd(a1,a2,,an)gcd(a1,a2,…,an) denotes the greatest common divisor (GCD) of integers a1,a2,,ana1,a2,…,an.

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

Two states (a1,a2,,an)(a1,a2,…,an) and (b1,b2,,bn)(b1,b2,…,bn) are considered different if there exists ii (1in1≤i≤n) such that aibiai≠bi.

Input

The first line contains two integers nn and mm (2n502≤n≤501m1051≤m≤105) — the number of stars and the upper bound of the sum of the brightness of stars.

Each of the next nn lines contains two integers lili and riri (1lirim1≤li≤ri≤m) — the range of the brightness of the ii-th star.

Output

Print a single integer — the number of different mathematical states of this constellation, modulo 998244353998244353.

Examples Mocha and Stars solution codeforces
input Mocha and Stars solution codeforces

Copy Mocha and Stars solution codeforces2 4
1 3
1 2
output

Copy
4
input

Copy
5 10
1 10
1 10
1 10
1 10
1 10
output

Copy
251
input

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

Copy
47464146
Note

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

  • a1=1a1=1a2=1a2=1.
  • a1=1a1=1a2=2a2=2.
  • a1=2a1=2a2=1a2=1.
  • a1=3a1=3a2=1a2=1.

 

Solution: Click here

 

Leave a Comment