Рассмотрим \(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\) и после каждого обновления вычислять требуемую суммарную стоимость. Каждое обновление меняет число, записанное ровно в одной клетке.
Выходные данные
Выведите \(q\) целых чисел, \(i\)-е из которых должно быть равно суммарной стоимости хороших путей после первых \(i\) обновлений. Так как эти числа могут быть большими, выводите их по модулю \(10^9 + 7\).
Примечание
Все хорошие пути в первом примере: \((1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4)\).
Изначально значения \(a\) равны \([3, 5, 1, 4, 2]\). После первого обновления — \([9, 5, 1, 4, 2]\). После второго обновления — \([9, 4, 1, 4, 2]\), и так далее.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2
|
62
58
78
86
86
|
|
2
|
5 2 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2
|
157
147
207
227
227
|
|
3
|
4 40 6
92 21 82 46
3 56
1 72
4 28
1 97
2 49
2 88
|
239185261
666314041
50729936
516818968
766409450
756910476
|