У Стека есть массив \(a\) длины \(n\) такой, что \(a_i = i\) для всех \(i\) (\(1 \leq i \leq n\)). Он выберет целое положительное число \(k\) (\(1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor\)) и выполнит следующую операцию над \(a\) любое число раз (возможно, \(0\)):
- Выбрать из \(a\) подпоследовательность\(^\dagger\) \(s\) длины \(2 \cdot k + 1\). Далее, удалить первые \(k\) элементов \(s\) из \(a\). Чтобы все было идеально сбалансировано (как и должно быть), также удалить последние \(k\) элементов \(s\) из \(a\).
Стеку стало интересно, сколько массивов \(a\) он может получить в итоге для каждого \(k\) (\(1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor\)). Поскольку Стек плохо справляется с математическими задачами, ему нужна ваша помощь.
Поскольку количество массивов может быть слишком большим, выведите его по модулю \(998\,244\,353\).
\(^\dagger\) Последовательность \(x\) является подпоследовательностью \(y\), если \(x\) может быть получена из \(y\) удалением нескольких (возможно, ни одного или всех) элементов. Например, \([1, 3]\), \([1, 2, 3]\) и \([2, 3]\) являются подпоследовательностями \([1, 2, 3]\). С другой стороны, \([3, 1]\) и \([2, 1, 3]\) не являются подпоследовательностями \([1, 2, 3]\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите \(\lfloor \frac{n-1}{2} \rfloor\) целых чисел, разделенных пробелами, где \(i\)-е число равняется количеству (по модулю \(998\,244\,353\)) массивов, которые Стек может получить, если выберет \(k=i\).
Примечание
В первом наборе входных данных для \(k=1\) возможны два \(a\):
Во втором наборе входных данных для \(k=1\) возможны четыре \(a\):
- \([1,2,3,4]\);
- \([1,3]\);
- \([2,3]\);
- \([2,4]\).
В третьем наборе входных данных для \(k=2\) возможны два \(a\):
- \([1,2,3,4,5]\);
- \([3]\).