E. Особые позиции
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Будучи школьником Стас очень грустил, когда рассадка в школьном автобусе не позволяла ему сесть рядом с другом, поэтому сейчас он вырос и начал писать программу, решающую эту проблему, и ему потребовалось решить такую задачу.

Дан массив $$$a$$$ длины $$$n$$$. Также даны $$$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}$$$.

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примеры
Входные данные
4 2
1 2 3 4
1 4
Выходные данные
665496247
Входные данные
6 6
4 2 4 2 4 2
1 2 3 4 5 6
Выходные данные
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$$$).