В Армии Байтляндии $$$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$$$).