E. Mocha и звезды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Mocha хочет быть астрологом. В небе над Чжицзяном $$$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$$$.

Mocha интересуется, сколько существует математических состояний этого созвездия. Так как ответ может быть большим, вы должны найти его по модулю $$$998\,244\,353$$$.

Два состояния $$$(a_1,a_2,\ldots,a_n)$$$ и $$$(b_1,b_2,\ldots,b_n)$$$ считаются различными, если существует индекс $$$i$$$ ($$$1\le i\le n$$$) такой, что $$$a_i \ne b_i$$$.

Входные данные

Первая строка содержит два целых числа $$$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$$$.

Примеры
Входные данные
2 4
1 3
1 2
Выходные данные
4
Входные данные
5 10
1 10
1 10
1 10
1 10
1 10
Выходные данные
251
Входные данные
5 100
1 94
1 96
1 91
4 96
6 97
Выходные данные
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$$$.