Mocha and Stars

time limit per test: 2 seconds

memory limit per test: 256 megabytes

Articles

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,…,a_n)$ to show its state. A state is called mathematical if all of the following three conditions are satisfied:

For all $i$ $(1≤i≤n)$ , $a_i$ is an integer in the range $l_i,r_i$ .
$∑_{i=1}^na_i≤m$ .
$gcd(a_1,a_2,…,a_n)=1$ .

Here, $gcd(a_1,a_2,…,a_n)$ denotes the greatest common divisor (GCD) of integers $a_1,a_2,…,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 $998244353$ .

Two states $(a_1,a_2,…,a_n)$ and $(b_1,b_2,…,b_n)$ are considered different if there exists $i$ $(1≤i≤n)$ such that $a_i≠b_i$ .

Input

The first line contains two integers $n$ and $m$ $(2≤n≤50, 1≤m≤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≤l_i≤r_i≤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 $998244353$ .

Examples

input

1
2
3

2 4
1 3
1 2

output

input

output

input

output

47464146

Note

In the first example, there are 44 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$ .

Tutorial

\large \begin{align*}\label{2} &\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}[\sum a_i \leq m][gcd(a_1,a_2,\cdots,a_n)=1] \\ =&\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}[\sum a_i \leq m]\sum_{d|gcd(a_1,\cdots,a_n)}\mu(d) \\ =&\sum_{d=1}^{m}\sum_{a_1=\lceil \frac{l_1}{d} \rceil}^{\lfloor \frac{r_1}{d} \rfloor}\sum_{a_2=\lceil \frac{l_2}{d} \rceil}^{\lfloor \frac{r_2}{d} \rfloor}\cdots\sum_{a_n=\lceil \frac{l_n}{d} \rceil}^{\lfloor \frac{r_n}{d} \rfloor}[\sum d\cdot a_i\leq m]\\ =&\sum_{d=1}^{m}\sum_{a_1=\lceil \frac{l_1}{d} \rceil}^{\lfloor \frac{r_1}{d} \rfloor}\sum_{a_2=\lceil \frac{l_2}{d} \rceil}^{\lfloor \frac{r_2}{d} \rfloor}\cdots\sum_{a_n=\lceil \frac{l_n}{d} \rceil}^{\lfloor \frac{r_n}{d} \rfloor}[\sum a_i\leq \lfloor \frac{m}{d} \rfloor]\\ \end{align*}

For each d, we can compute it in $O(n\frac{m}{d})$ by Knapsack DP optimized by prefix-sums. So we can compute it in $O(n∑_{d=1}^{m}⌊\frac{m}{d}⌋)=O(nmlogm)$ .

Code

#include<bits/stdc++.h>

using namespace std;

const int mod = 998244353;
const int maxn = 1e5+1;

int l[maxn], r[maxn];
long long dp[51][maxn];
long long prime[maxn], tot, mu[maxn];
bool vis[maxn];

void get_prime(int n) {
    mu[1] = 1;
    vis[1] = true;
    for(int i = 2; i <= n; ++ i) {
        if (!vis[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1; i * prime[j] <= n; ++ j) {
            vis[i*prime[j]] = true;
            if (i % prime[j] == 0) break;
            mu[i*prime[j]] = mu[i] * mu[prime[j]];
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) {
        cin >> l[i] >> r[i];
    }
    for(int i = 0; i <= m; ++ i) {
        dp[0][i] = 1;
    }
    get_prime(m);
    long long ans = 0;
    for(int d = 1; d <= m; ++ d) {
        int M = m/d, flag = 1;
        if (mu[d] == 0 || M == 0) continue;
        for(int i = 1; i <= n; ++ i) {
            int x = (l[i]+d-1)/d, y = r[i]/d;
            if (x > y) {
                flag = 0;
                break;
            }
            for(int j = 1; j <= M; ++ j) {
                dp[i][j] = 0;
                if (x <= j) dp[i][j] = (dp[i][j] + dp[i-1][j-x]) % mod;
                if (y < j) dp[i][j] = (mod + (dp[i][j] - dp[i-1][j-y-1])%mod) %mod;
                dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod;
            }
        }
        if (flag) ans = (ans + mod + mu[d] * dp[n][M]) % mod;
    }
    cout << ans << "\n";
}