F. Пульс
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$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$$$.

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

Первая строка содержит целое число $$$n$$$ ($$$1\le n\le 700$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,\ldots,a_n$$$ ($$$0\le a_i<998\,244\,353$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1,\ldots,b_n$$$ ($$$0\le b_i<998\,244\,353$$$).

Четвертая строка содержит $$$n$$$ целых чисел $$$c_0,\ldots,c_{n-1}$$$ ($$$0\le c_i<998\,244\,353$$$).

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

Выведите $$$n$$$ целых чисел: $$$i$$$-е из них — $$$f(i)$$$ по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3
1 1 1
1 1 1
1 1 1
Выходные данные
1 2 6
Входные данные
3
1 2 3
2 3 1
3 1 2
Выходные данные
6 13 34
Входные данные
5
1 4 2 5 3
2 5 1 3 4
300000000 100000000 500000000 400000000 200000000
Выходные данные
600000000 303511294 612289529 324650937 947905622
Примечание

Во втором примере:

  • Рассмотрим перестановку $$$[1,2,3]$$$. Индексы $$$1,2,3$$$ являются префиксными максимумами. Индекс $$$3$$$ — единственный суффиксный максимум. Индексы $$$2,3$$$ — подъемы. В итоге, у нее $$$3$$$ префиксных максимума, $$$1$$$ суффиксный максимум и $$$2$$$ подъема. Поэтому ее стоимость равна $$$a_3b_1c_2=12$$$.
  • Перестановка $$$[1,3,2]$$$ имеет $$$2$$$ префиксных максимума, $$$2$$$ суффиксных максимума и $$$1$$$ подъем. Ее стоимость равна $$$6$$$.
  • Перестановка $$$[2,1,3]$$$ имеет $$$2$$$ префиксных максимума, $$$1$$$ суффиксный максимум и $$$1$$$ подъем. Ее стоимость равна $$$4$$$.
  • Перестановка $$$[2,3,1]$$$ имеет $$$2$$$ префиксных максимума, $$$2$$$ суффиксных максимума и $$$1$$$ подъем. Ее стоимость равна $$$6$$$.
  • Перестановка $$$[3,1,2]$$$ имеет $$$1$$$ префиксный максимум, $$$2$$$ суффиксных максимума и $$$1$$$ подъем. Ее стоимость равна $$$3$$$.
  • Перестановка $$$[3,2,1]$$$ имеет $$$1$$$ префиксный максимум, $$$3$$$ суффиксных максимума и $$$0$$$ подъемов. Ее стоимость равна $$$3$$$.

Сумма стоимостей всех перестановок равна $$$34$$$, поэтому $$$f(3)=34$$$.