题目描述

小灰灰面前按顺序摆着 $n$ 份材料，第 $i$ 份材料的类别为 $c_i$，页数为 $w_i$．

他准备从中选出至少一份材料，保持它们原来的先后顺序，再将选出的材料分批装订．相邻且类别相同的材料必须装订在同一批中；相邻且类别不同的材料必须分属不同的批次．

本次装订按以下规则计费：一批材料的费用为这一批材料总页数的平方．一种选取方案的费用，等于所有批次的装订费用之和．

请计算所有选取方案的费用之和，答案对 $998244353$ 取模．

只要选取的位置集合不同，就视为不同方案．注意，未选取的材料不会隔开批次：原本不相邻的两份同类材料，可能在选取后被装订在同一批中．

输入格式

第一行输入一个整数 $n$．

第二行输入 $n$ 个整数 $c_1,c_2,\ldots,c_n$．

第三行输入 $n$ 个整数 $w_1,w_2,\ldots,w_n$．

输出格式

输出一个整数，表示答案对 $998244353$ 取模的结果．

样例 1

输入

3
1 2 1
1 2 3

输出

62

解释

只选一份材料的三个方案，费用之和为 $1+4+9=14$．

选两份材料时：

• 选第 $1,2$ 份，分为两批，费用为 $1^2+2^2=5$．
• 选第 $1,3$ 份，装订在同一批中，费用为 $(1+3)^2=16$．
• 选第 $2,3$ 份，分为两批，费用为 $2^2+3^2=13$．

三份全部选取时分为三批，费用为 $1^2+2^2+3^2=14$．

答案为 $14+5+16+13+14=62$．

样例 2

输入

3
2 2 2
1 1 1

输出

24

解释

选一份、两份、三份的方案数分别为 $3,3,1$，每种方案的费用分别为 $1,4,9$．

数据规模与约定

对于所有数据，$1\le n\le 2\times10^5$，$1\le c_i\le n$，$1\le w_i\le10^9$．

本题采用捆绑测试，各子任务相互独立．

子任务	分数	附加限制
1	15	$n\le18$
2	10	所有 $c_i$ 互不相同
3		所有 $c_i$ 相同
4	20	$n\le2500$
5		$c_i\le20$
6	25	无

下发样例

• Data/sample1.in 与 Data/sample1.ans：题面中的样例 1．
• Data/sample2.in 与 Data/sample2.ans：题面中的样例 2．
• Data/sample3.in 与 Data/sample3.ans：满足子任务 1 的附加限制．
• Data/sample4.in 与 Data/sample4.ans：满足子任务 2 的附加限制．
• Data/sample5.in 与 Data/sample5.ans：满足子任务 3 的附加限制．
• Data/sample6.in 与 Data/sample6.ans：满足子任务 4 的附加限制．
• Data/sample7.in 与 Data/sample7.ans：满足子任务 5 的附加限制．
• Data/sample8.in 与 Data/sample8.ans：该样例无特殊限制．
• Data/sample9.in 与 Data/sample9.ans：该样例无特殊限制．

大样例下载

点击下载本题选手目录