Tras una intensa colaboración entre los concursantes de física e informática, lograron terminar un gran proyecto: "El robot Machin".

El robot Machin opera dentro de una sala que se puede representar como un arreglo ~a~ de tamaño ~n~, donde cada posición de la sala tiene un entero ~a_i~. Si Machin está en la posición número ~i~ el se puede mover a la posición ~i+1~ o ~i-1~, siempre y cuando no se salga de los límites de la sala (~1~ y ~n~). Además el robot Machin está configurado para moverse exactamente ~k~ veces.

Sea ~c_0, c_1, ..., c_k~, las posiciones formadas por alguna secuencia de movimientos del robot Machin, donde ~c_0~ es la posición inicial y ~c_i~ es la posición donde se encontrará luego de ~i~ movimientos. Dicha secuencia la llamaremos camino bueno, la cual también tiene asociado un valor: ~a_{c_0} + a_{c_1} + ... + a_{c_k}~.

El valor de la sala, es igual a la suma del valor de todos los caminos buenos que puede formar Machin. Dos caminos se consideran diferentes si en algún punto ~i~ el robot se encontrará en posiciones distintas. Debido a que el valor de la sala puede llegar a ser muy grande los creadores del proyecto lo toman módulo ~10^9+7~.

En su afán por la ciencia, ellos hacen ~q~ actualizaciones, y en cada una escogen un índice ~i~ y un valor ~x~ para hacer ~a_i:=x~. Así que ahora tienen un grave problema, cual será el valor de la sala luego de la ~i~-ésima actualización?

Entrada

La primera línea de entrada contiene 3 enteros ~n~, ~k~ y ~q~ (~2 \le n \le 5000~; ~1 \le k \le 5000~; ~1 \le q \le 2 \cdot 10^5~), el tamaño de la sala, el entero con el que está configurado el robot Machin y la cantidad de actualizaciones respectivamente.

La segunda línea contiene ~n~ enteros ~a_1, a_2,...,a_n~ (~1 \le a_i \le 10^9~).

Seguido de ~q~ líneas cada una con dos enteros separados por espacios: ~i~ y ~x~ (~1 \le i \le n~; ~1 \le x \le 10^9~) que indican que debes cambiar el valor de ~a_i~ por ~x~.

Salida

Imprima ~q~ líneas, cada una con un único entero, el valor de la sala tras la ~i~-ésima actualización (note que las actualizaciones se mantienen). Debido a que puede ser un entero demasiado grande, de el resultado modulo ~10^9+7~.

Puntuación

Subtarea	Condiciones	Puntos	Dependencias
~1~	~1 \le n,k \le 10~ , ~1 \le q \le 100~	~15~	~-~
~2~	~1 \le n, k, q \le 100~	~25~	~1~
~3~	~-~	~60~	~2~

Ejemplos

Entrada de ejemplo 1

5 1 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2

Salida de ejemplo 1

62
58
78
86
86

Explicación ejemplo 1

En el primer ejemplo los caminos buenos son: ~(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4)~.

Inicialmente los valores de a son: ~[3,5,1,4,2]~. Luego de la primera actualización el arreglo se convierte en: ~[9,5,1,4,2]~. Luego de la segunda el arreglo a es igual a: ~[9,4,1,4,2]~, y así sucesivamente.

Entrada de ejemplo 2

5 2 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2

Salida de ejemplo 2

157
147
207
227
227

Entrada de ejemplo 3

4 40 6
92 21 82 46
3 56
1 72
4 28
1 97
2 49
2 88

Salida de ejemplo 3

239185261
666314041
50729936
516818968
766409450
756910476