В Армии Байтляндии \(n\) офицеров. У каждого офицера есть некоторая сила. Сила \(i\)-го офицера равна \(p_{i}\). Так как война приближается, Генерал хотел бы узнать силу армии.
Сила армии определяется очень странно в Байтляндии. Генерал выбирает случайное подмножество офицеров с этих \(n\) офицеров, и называет его батальоном. (Все \(2^n\) подмножеств \(n\) офицеров могут быть выбраны с равной вероятностью, включая пустое подмножество и множество всех офицеров).
Сила батальона определяется следующим образом:
Пусть силы выбранных офицеров равны \(a_{1},a_{2},\ldots,a_{k}\), где \(a_1 \le a_2 \le \dots \le a_k\). Сила этого батальона равняется \(a_1a_2 + a_2a_3 + \dots + a_{k-1}a_k\). (Если размер батальона \(\leq 1\), сила этого батальона равна \(0\)).
Сила армии равна матожиданию силы батальона.
Так как война очень длинная, силы офицеров могут измениться. А именно, будет \(q\) изменений. Каждое изменение будет иметь вид \(i\) \(x\), показывающий, что \(p_{i}\) стало равным \(x\).
Вы должны найти силу армии в самом начале, а также после каждого из \(q\) изменений.
Заметьте, что изменения необратимы.
Вы должны найти силу по модулю \(10^{9}+7\). Более формально, пусть \(M=10^{9}+7\). Можно показать, что ответ можно выразить как несократимую дробь \(p/q\), где \(p\) и \(q\) целые и \(q\not\equiv 0 \bmod M\)). Выведите число, равное \(p\cdot q^{-1} \bmod M\). Другими словами, выведите число \(x\) такое, что \(0 \leq x < M\) и \(x ⋅ q \equiv p \bmod M\)).
Выходные данные
В первой строке, выведите начальную силу армии.
В \(i\)-й из следующих \(q\) строк, выведите силу армии после \(i\)-о изменения.
Примечание
В первом примере, изначально есть четыре возможных батальона
- {} Сила = \(0\)
- {\(1\)} Сила = \(0\)
- {\(2\)} Сила = \(0\)
- {\(1,2\)} Сила = \(2\)
Поэтому матожидание силы армии равно
\(\frac{0+0+0+2}{4}\) =
\(\frac{1}{2}\)После изменения \(p_{1}\) на \(2\), сила батальона {\(1,2\)} становится равной \(4\), поэтому сила армии становится равной \(1\).
После изменения \(p_{2}\) на \(1\), сила батальона {\(1,2\)} опять становится \(2\), поэтому сила армии становится равной \(\frac{1}{2}\).