给定一个长度为 $$$n$$$ 的数组 $$$a$$$。此外,您还会获得 $$$m$$$ 不同的位置 $$$p_1、p_2、\ldots、p_m$$$ ($$$1 \leq p_i \leq n$$$)。
这些位置 $$$T$$$ 的非空子集以等概率随机选择,并计算以下值: $$$$$$\sum_{i=1}^{n} (a_i \cdot \min_{j \in T} \left|i - j\right|)。$$$$$$ 换句话说,对于数组的每个索引,$$$a_i$$$ 和到最近的距离所选位置相乘,然后将这些值相加。
求该总和的期望值。
该值必须对 $$$998\,244\,353$$$ 求模。更正式地说,让 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \neq 0$$$ (mod $$$M$$$)。输出等于 $$$p \cdot q^{-1}$$$ (mod $$$M$$$) 的整数。换句话说,输出这样的整数 $$$x$$$ 使得 $$$0 \leq x < M$$$ 且 $$$x \cdot q = p$$$ (mod $$$M$$$)。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 998\,244\,353$$$)。
第三行包含 $$$m$$$ 不同的整数 $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \le n$$$)。
对于每个$$$1 \leq i < m$$$,保证$$$p_i < p_{i+1}$$$。
输出
打印一个整数——问题的答案。
示例
输入 #1
4 2 1 2 3 4 1 4
输出 #1
665496247
输入 #2
6 6 4 2 4 2 4 2 1 2 3 4 5 6
输出 #2
855638030
注意
在第一个测试中:
- 如果仅选择 $$$1$$$,则该值等于 $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 20$$$。
- 如果仅选择 $$$4$$$,则该值等于 $$$1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 + 4 \cdot 0 = 10$$$。
- 如果选择了两个位置,则该值等于 $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 = 5$$$。
问题的答案是 $$$\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$$$ (模 $$$998\,244\,353$$$)。