对于数组 $$$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$$$。
示例
输入 #1
3 1 1 1 1 1 1 1 1 1
输出 #1
1 2 6
输入 #2
3 1 2 3 2 3 1 3 1 2
输出 #2
6 13 34
输入 #3
5 1 4 2 5 3 2 5 1 3 4 300000000 100000000 500000000 400000000 200000000
输出 #3
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$$$。