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\).
Выходные данные
Выведите одно целое число — количество различных математических состояний созвездия по модулю \(998\,244\,353\).