#P1641E. Special Positions

    ID: 111 远端评测题 5000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>combinatoricsdivide and conquerfftmath*3300

Special Positions

Description

You are given an array aa of length nn. Also you are given mm distinct positions p1,p2,,pmp_1, p_2, \ldots, p_m (1pin1 \leq p_i \leq n).

A non-empty subset of these positions TT is randomly selected with equal probability and the following value is calculated: i=1n(aiminjTij).\sum_{i=1}^{n} (a_i \cdot \min_{j \in T} \left|i - j\right|). In other word, for each index of the array, aia_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 998244353998\,244\,353. More formally, let M=998244353M = 998\,244\,353. It can be shown that the answer can be represented as an irreducible fraction pq\frac{p}{q}, where pp and qq are integers and q0q \neq 0 (mod MM). Output the integer equal to pq1p \cdot q^{-1} (mod MM). In other words, output such integer xx that 0x<M0 \leq x < M and xq=px \cdot q = p (mod MM).

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

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai<9982443530 \leq a_i < 998\,244\,353).

The third line contains mm distinct integers p1,p2,,pmp_1, p_2, \ldots, p_m (1pin1 \leq p_i \le n).

For every 1i<m1 \leq i < m it is guaranteed that pi<pi+1p_i < p_{i+1}.

Print a single integer — the answer to the problem.

Input

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

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai<9982443530 \leq a_i < 998\,244\,353).

The third line contains mm distinct integers p1,p2,,pmp_1, p_2, \ldots, p_m (1pin1 \leq p_i \le n).

For every 1i<m1 \leq i < m it is guaranteed that pi<pi+1p_i < p_{i+1}.

Output

Print a single integer — the answer to the problem.

Samples

样例输入 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

Note

In the first test:

  • If only 11 is choosen, than the value equals to 10+21+32+43=201 \cdot 0 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 20.
  • If only 44 is choosen, than the value equals to 13+22+31+40=101 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 + 4 \cdot 0 = 10.
  • If both positions are chosen, than the value equals to 10+21+31+40=51 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 = 5.

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