Los azucareros del centro son amantes de los arreglos más grandes, o sea, que si ~Y~ y ~Z~ son dos arreglos de la misma longitud, podemos decir que el arreglo Y es más grande que el arreglo ~Z~ si ~Y_i > Z_i~ para todo i.

Ejemplo 1 Ejemplo 2 Ejemplo 3

~Y = [8,9,5,9]~ ~Y = [3,9,4,5]~ ~Y = [3,9,5,9]~

~Z = [7,6,3,5]~ ~Z = [2,5,6,7]~ ~Z = [2,6,5,4]~

• En el primer ejemplo, ~Y~ es más grande que ~Z~.

• En el segundo ejemplo, Y no es más grande que ~Z~, ya que ~Y_4~ no es más grande que ~Z_4~.

• En el tercer ejemplo, Y no es más grande que ~Z~, ya que ~Y_3~ no es más grande que ~Z_3~.

Si ~S~ es un arreglo de enteros, ~F(S)~ será definida como sigue. Considere todos los posibles arreglos de enteros ~X~ con la misma longitud que S tal que ~1 \le X_i \le S_i~ para toda posición ~i~. Entonces ~F(S)~ es el número máximo de tales arreglos que puedes escribir tal que ningún arreglo es más grande que otro arreglo en la lista. Dos arreglos Y y Z se consideran diferentes si hay al menos una posición ~i~ donde \(Y_i ≠ Z_i\).

Por ejemplo, ~F([2,3]) = 4~, ya que usted puede escribir los siguientes cuatro arreglos: ~[2,2], [2,3], [1,3], [2.1]~. Note que ningún arreglo es más grande que cualquier otro arreglo en la lista. Además, usted puede verificar que si usted escribe más de 4 arreglos, entonces siempre habrá un arreglo que es más grande que algún otro arreglo en la lista. Por tanto, ~F([2,3])=4~.

A usted se le dará un arreglo ~A = [A_1, A_2,...,A_n]~ con ~n~ elementos. Usted necesita procesar ~q~ preguntas (en lo adelante query o queries). Hay dos tipos de queries:

~1 l r x~ : Asignar cada elemento de la posición ~l~ a la ~r~ del arreglo ~A~ con el valor ~x~. poner ~A_i~ igual a ~x~ para ~l \le i \le r~.

~2 l r~ : Sea el arreglo ~B~ un subarreglo del arreglo ~A~ de la posición ~l~ a ~r~. Encuentre \(F(B) módulo 10^9 + 7 \).

Entrada

La primera línea contiene dos enteros ~n~ y ~q~ separados entre sí por espacio, el número de elementos en el arreglo y el número de queries, respectivamente. La próxima línea contiene ~n~ enteros ~A_1, A_2, ..., A_n~ denotando los elementos del arreglo ~A~, separados entre sí por espacio. Las próximas ~q~ líneas describen las queries. Cada query se describe como una línea simple la cual comienza con un número ~t~ denotando el tipo de query. Entonces:

• Si ~t=1~, a continuación aparecen tres enteros ~l~, ~r~ y ~x~.

• Si ~t=2~, a continuación aparecen dos enteros ~l~ y ~r~.

Salida

Para cada query del tipo 2 imprima una línea simple conteniendo a un entero que denote la respuesta para esa query módulo ~10^9 + 7~.

Restricciones

\(• 1 \le n, q \le 10^5\)

\(• 1 \le A_i, x \le 10^9\)

\(• 1 \le l \le r \le n\)

\(• 1 \le t \le 2\)

Ejemplo de Entrada

5 4
1 1 3 4 5
1 1 2 2
2 2 3
1 2 5 3
2 1 2

Ejemplo de Salida

4
4

Explicación del ejemplo:

Nosotros tenemos ~n=5~ y ~A=[1,1,3,4,5]~. Hay q=4 queries:

1. La primera query es del tipo ~t=1~, y tenemos ~l=1, r=2~ y ~x=2~, lo que significa que necesitamos asignar a ~A_1~ y ~A_2~ el valor de 2. Por lo tanto, después de esta query, el arreglo ~A~ es ahora ~A = [2,2,3,4,5]~.

2. La segunda query es del tipo ~t=2~, y tenemos ~l=2~ y ~r=3~. ~B~ está definido como un subarreglo de ~A~ desde la posición 2 a la posición 3, por lo tanto ~B = [2,3]~. Como se explicó arriba F([2,3]) = 4, así que imprimimos ~4 mod (10^9 + 7) = 4~.

3. La tercera query es del tipo ~t=1~, y tenemos ~l=2, r=5~ y ~x=3~, lo que significa que necesitamos asignar a ~A_2, A_3, A_4~ y ~A_5~ el valor de 3. Por lo tanto, después de esta query, el arreglo ~A~ es ahora ~A = [2,3,3,3,3]~.

4. La cuarta query es del tipo ~t=2~, y tenemos ~l=1~ y ~r=2~. ~B~ está definido como un subarreglo de A desde la posición ~1~ a la posición 2, por lo tanto ~B = [2,3]~. Como se explicó arriba ~F([2,3]) = 4~, así que imprimimos ~4 mod (10^9 + 7) = 4~.