Al perrito chill no le gustan mucho las funciones, y su profesor le ha dejado muchas de tarea!

Las funciones tienen la forma: ~f(x) = ax + b~ y su profesor le hace varias consultas como: Añade esta función o reemplaza esta función, o calcula el valor de ~a(b(...c(v)))~ (la función compuesta evaluada en un valor ~v~ dado).

Ayude al perrito a resolver la tarea!

Entrada

La primera línea contiene un entero ~t~, la subtarea actual.

La segunda línea contiene un entero, ~q~, la cantidad de consultas.

A partir de ahí hay ~q~ líneas cada una empieza con un entero ~o~ (operación)

Si ~o=1~ entonces le siguen dos números: ~a~ y ~b~, debes añadir la función ~f(x) = ax + b~ a la lista.

Si ~o=2~ entonces le siguen tres números: ~i~, ~a~, ~b~, debes reemplazar la función que ocupa el lugar ~i~ con ~f(x) = ax + b~

Si ~o=3~ entonces le sigue un único entero: ~v~, debes hallar la función compuesta de todas las funciones en la lista y evaluarla en ~v~ modulo ~10^9+7~.

Salida

Por cada consulta de tipo ~o=3~ debes imprimir un entero, el resultado de la operación modulo ~10^9+7~

Restricciones

~t \in \{ 1, 2, 3, 4, 5 \}~

~1 \le q \le 2 \cdot 10^5~

~1 \le i \le 2 \cdot 10^5~

~o \in \{ 1, 2, 3 \}~

~0 \le a, b, v \le 10^9~

Subtareas

• (3 pt) La primera consulta será una inserción y lo demás seran consultas de tipo ~o=3~

• (3 pt) La primera consulta será una inserción y lo demás seran operaciones de tipo ~o=2~ y ~o=3~

• (6 pt) Habrá multiples inserciones y consultas de tipo ~o=3~

• (23 pt) Habrá a lo más ~100~ inserciones y ~100~ reemplazos, lo demás seran consultas.

• (65 pt) Sin restricciones adicionales.

Ejemplo de entrada 1

1
4
1 17 2
3 2
3 1
3 0

Ejemplo de salida 1

36
19
2

Explicación de salida 1

Estas son las cuatro consultas:

1. (~o=1~) Se inserta la función ~a(x) = 17x + 2~

2. (~o=3~) Se evalúa la función en 2: ~f(2) = 17 \cdot 2 + 2 = 36~ y se imprime en consola

3. (~o=3~) Se evalúa la función en 1: ~f(1) = 17 \cdot 1 + 2 = 19~ y se imprime en consola

4. (~o=3~) Se evalúa la función en 0: ~f(0) = 17 \cdot 0 + 2 = 2~ y se imprime en consola

Ejemplo de entrada 2

5
7
1 2 1
3 5
3 6
1 1 1
3 3
2 1 1 1
3 10

Ejemplo de salida 2

11
13
9
12

Explicación de salida 2

Las operaciones:

1. (~o=1~) Se inserta la función ~a(x) = 2x + 1~

2. (~o=3~) Se evalúa la función en 5: ~a(5) = 2\cdot 5 + 1 = 11~ y se imprime

3. (~o=3~) Se evalúa la función en 6: ~a(6) = 2 \cdot 6 + 1 = 13~ y se imprime

4. (~o=1~) Se añade la función: ~b(x) = x+1~

5. (~o=3~) Se evalúa la función compuesta en 3: ~a(b(3)) = a(3+1) = a(4) = 2 \cdot 4 + 1 = 9~

6. (~o=2~) Se reemplaza la función 1 (la ~a(x)~) con la función: ~a(x) := x+1~

7. (~o=3~) Se evalúa la función en 10: ~a(b(10)) = a(10+1) = a(11) = 11+1 = 12~