Для массива \(u_1, u_2, \ldots, u_n\) определим
- префиксный максимум как такой индекс \(i\), что \(u_i>u_j\) для всех \(j<i\);
- суффиксный максимум как такой индекс \(i\), что \(u_i>u_j\) для всех \(j>i\);
- подъем как такой индекс \(i\) (\(i>1\)), что \(u_i>u_{i-1}\).
У вас есть три массива стоимостей: \([a_1, a_2, \ldots, a_n]\), \([b_1, b_2, \ldots, b_n]\) и \([c_0, c_1, \ldots, c_{n-1}]\).
Определим стоимость массива, имеющего \(x\) префиксных максимумов, \(y\) суффиксных максимумов и \(z\) подъемов, как \(a_x\cdot b_y\cdot c_z\).
Пусть сумма стоимости всех перестановок \(1,2,\ldots,n\) равна \(f(n)\). Найдите \(f(1)\), \(f(2)\), ..., \(f(n)\) по модулю \(998\,244\,353\).