Будучи школьником Стас очень грустил, когда рассадка в школьном автобусе не позволяла ему сесть рядом с другом, поэтому сейчас он вырос и начал писать программу, решающую эту проблему, и ему потребовалось решить такую задачу.
Дан массив \(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\)).
Примечание
В первом примере:
- Если взята только позиция \(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\)).