Это простая версия задачи. Единственные различия между двумя версиями этой задачи — ограничения на \(t\), \(m\) и сумму \(m\). Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Для массива целых чисел \(a\) длины \(n\) определим \(f(k)\) как наибольший общий делитель (НОД) максимальных значений всех подмассивов\(^{\text{∗}}\) длины \(k\). Например, если массив равен \([2, 1, 4, 6, 2]\), то \(f(3) = \operatorname{gcd}(\operatorname{max}([2, 1, 4]), \operatorname{max}([1, 4, 6]), \operatorname{max}([4, 6, 2])) = \operatorname{gcd}(4, 6, 6) = 2\).
Массив является хорошим, если для всех пар \(1 \le i \lt j \le n\) выполняется \(f(i) \neq f(j)\).
У Shohag есть целое число \(m\). Помогите ему подсчитать количество непустых хороших массивов произвольной длины, каждый элемент которых является целым числом от \(1\) до \(m\), по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите целое число — количество подходящих массивов по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных подходящими массивами являются \([1]\), \([1, 2]\), \([2]\) и \([2, 1]\).
Во втором наборе входных данных всего \(29\) подходящих массивов. В частности, массив \([2, 1, 4]\) длины \(n = 3\) подходит, так как все его элементы принадлежат отрезку от \(1\) до \(m = 5\) и \(f(1)\), \(f(2)\) и \(f(n = 3)\) различны:
- \(f(1) = \operatorname{gcd}(\operatorname{max}([2]), \operatorname{max}([1]), \operatorname{max}([4])) = \operatorname{gcd}(2, 1, 4) = 1.\)
- \(f(2) = \operatorname{gcd}(\operatorname{max}([2, 1]), \operatorname{max}([1, 4])) = \operatorname{gcd}(2, 4) = 2.\)
- \(f(3) = \operatorname{gcd}(\operatorname{max}([2, 1, 4])) = \operatorname{gcd}(4) = 4.\)