Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fibonotci es una sequencia de enteros recursiva definida de la siguiente manera:
$F_n = S_{n-1}*F_{n-1} + S_{n-2}*F_{n-2}$

$F_1 = 0;$
$F_2 = 1;$

Nuestra tarea aqui es simple, dada la secuencia $S$ y $Q$ operaciones de la forma:
$p$ $v$
debemos remplazar el elemento de $S$ que se encuentra en la posición $p$ por el entero $v$.

Queremos conocer el valor de $F_n$ luego de cada operación.
Como los valores de $F_n$ pueden ser muy grandes mejor computarlo módulo $1000000007$;

Input

La primera línea de la entrada contiene un entero $N$, la cantidad de elementos de $S$.
En la línea siguiente tendremos $N$ numeros enteros $S_i$ $(S_i \le 10^9)$, los elementos de la secuencia $S$.
La siguiente línea de la entrada contiene un entero $Q$, la cantidad de operaciones.
La siguientes $Q$ líneas de la entrada contiene dos enteros $p$ $v$, la posición y el valor de la operación.

Output

La primera línea de la salida contiene el valor de $F_n$ sin aplicar ninguna operación.
La siguientes Q líneas de la salida contiene el valor de $F_n$ luego de aplicar la i-ésima operación.

$N \le 100000$
$Q \le 100000$

Sample test(s)