Рассмотрим $$$n$$$ клеток, пронумерованных числами $$$1,2,\dots, n$$$ слева направо. Вы можете изначально в любую из этих клеток поставить робота, который затем должен сделать ровно $$$k$$$ шагов.

За один шаг робот перемещается в соседнюю клетку слева или справа, при этом он не может выходить за границы заданных клеток. Иными словами, если робот был в клетке $$$i$$$, он должен переместиться либо в клетку $$$i-1$$$, либо в клетку $$$i+1$$$, при этом клетка, в которую он перемещается, должна иметь номер от $$$1$$$ до $$$n$$$ (включительно). Клетки в том порядке, в котором робот их посещает (включая стартовую клетку), вместе составляют хороший путь.

В каждой клетке записано целое число — в клетке $$$i$$$ записано число $$$a_i$$$. Пусть $$$c_0, c_1, \dots, c_k$$$ — последовательность клеток в хорошем пути в том порядке, в котором они были посещены ($$$c_0$$$ — клетка, где был робот изначально, $$$c_1$$$ — клетка, в которой он оказался после первого шага, и так далее; более формально, $$$c_i$$$ — клетка, в которой оказался робот после $$$i$$$ шагов). Тогда стоимость пути вычисляется по следующей формуле: $$$a_{c_0} + a_{c_1} + \dots + a_{c_k}$$$.

Ваша задача — посчитать суммарную стоимость всех хороших путей. Так как это число может быть очень большим, его надо выводить по модулю $$$10^9 + 7$$$. Два хороших пути различны, если либо различается стартовая клетка, либо существует такое $$$i \in [1, k]$$$, что местоположение робота после $$$i$$$ шагов различается в этих путях.

Также вам нужно обрабатывать $$$q$$$ обновлений значений $$$a$$$ и после каждого обновления вычислять требуемую суммарную стоимость. Каждое обновление меняет число, записанное ровно в одной клетке.