CF1641E.Special Positions

You are given an array $a$ of length $n$. Also you are given $m$ distinct positions $p_1, p_2, \ldots, p_m$ ($1 \leq p_i \leq n$).

A non-empty subset of these positions $T$ is randomly selected with equal probability and the following value is calculated: $$\sum_{i=1}^{n} (a_i \cdot \min_{j \in T} \left|i - j\right|).$$ In other word, for each index of the array, $a_i$ and the distance to the closest chosen position are multiplied, and then these values are summed up.

Find the expected value of this sum.

This value must be found modulo $998\,244\,353$. More formally, let $M = 998\,244\,353$. It can be shown that the answer can be represented as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \neq 0$ (mod $M$). Output the integer equal to $p \cdot q^{-1}$ (mod $M$). In other words, output such integer $x$ that $0 \leq x \lt M$ and $x \cdot q = p$ (mod $M$).

给你一个长度为 $n$ 的数组 $a$，以及 $m$ 个互不相同的位置 $p_1, p_2, \ldots, p_m$（满足 $1 \leq p_i \leq n$）。

从这些位置中非空子集 $T$ 被等概率随机选取，并计算如下值：

$$\sum_{i=1}^{n} \left(a_i \cdot \min_{j \in T} \left|i - j\right|\right).$$

换言之，对数组的每个下标 $i$，将 $a_i$ 与它到所选位置集合 $T$ 中最近位置的距离相乘，再将所有这些乘积求和。

请计算该和的期望值。

答案需对 $998\,244\,353$ 取模。更准确地说，令 $M = 998\,244\,353$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not\equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。即，输出满足 $0 \leq x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

The first line contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 998\,244\,353$).

The third line contains $m$ distinct integers $p_1, p_2, \ldots, p_m$ ($1 \leq p_i \le n$).

For every $1 \leq i \lt m$ it is guaranteed that $p_i \lt p_{i+1}$.

第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \lt 998\,244\,353$）。

第三行包含 $m$ 个互不相同的整数 $p_1, p_2, \ldots, p_m$（$1 \leq p_i \le n$）。

对于每个 $1 \leq i \lt m$，保证有 $p_i \lt p_{i+1}$。

Print a single integer — the answer to the problem.

输出一个整数——该问题的答案。

In the first test:

• If only $1$ is choosen, than the value equals to $1 \cdot 0 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 20$.
• If only $4$ is choosen, than the value equals to $1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 + 4 \cdot 0 = 10$.
• If both positions are chosen, than the value equals to $1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 = 5$.

The answer to the problem is $\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$ (modulo $998\,244\,353$).

在第一个测试中：

• 如果只选择 $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$ 取模）。