Codeforces Round 773 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

divide and conquer

fft

math

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Special Positions

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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 < M$$$ and $$$x \cdot q = p$$$ (mod $$$M$$$).

Input

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 < 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 < m$$$ it is guaranteed that $$$p_i < p_{i+1}$$$.

Output

Print a single integer — the answer to the problem.

Examples

Input

4 2 1 2 3 4 1 4

Output

665496247

Input

6 6 4 2 4 2 4 2 1 2 3 4 5 6

Output

855638030

Note

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$$$).

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 06:36:14 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|