Cálculos extraños y Gatos

El universo de Max es una mesa que consta de n filas y m columnas.  Tanto las filas como las columnas están marcadas con números enteros consecutivos que comienzan con 1.  Utilizaremos (r, c) para designar una celda ubicada en la fila r y la columna c.

Max a menudo es invitado a alguna parte de la mesa.  Cada vez que recibe una invitación, primero calcula la cantidad de formas de llegar a este lugar, y solo entonces se va.  La casa de Max está ubicada en la celda (1, 1).

En cualquier momento, Max se mueve de la celda en la que se encuentra actualmente a una celda adyacente (dos celdas son adyacentes si comparten un lado común).  Por supuesto, el movimiento solo es posible si existe dicha celda, es decir, Max no irá más allá de los límites de la mesa.  Por lo tanto, desde la celda (r,  c) es capaz de moverse hacia una de las celdas (r -1,  c), (r,  c -1),        (r  + 1, c), (r,  c  + 1).  Además, Max puede omitir un movimiento y permanecer en la celda actual (r, c).

Además del amor por los cálculos extraños,  Max es alérgico a los gatos, por lo que nunca va a la celda que tiene un gato.  Max sabe exactamente dónde y cuándo será invitado y el horario de los gatos que viajan a lo largo de la mesa.  Formalmente, tiene q registros, el i -ésimo tiene una de las siguientes formas:

• 1, x_i, y_i, t_i  - Max está invitado a ir a la celda (x_i,  y_i) en el momento t_i.  Se garantiza que no hay ningún gato dentro de la celda (x_i,  y_i) en este momento.
• 2, x_i, y_i, t_i  - en el momento t_i  aparece un gato en la celda (x_i,  y_i).  Se garantiza que ningún otro gato se encuentra en esta celda (x_i,  y_i) en ese momento.
• 3, x_i, y_i, t_i  - en el momento t_i un gato deja de células (x_i,  y_i).  Se garantiza que hay un gato ubicado en la celda (x_i,  y_i).

Max planea aceptar solo una invitación, pero aún no ha decidido cuál es la particular.  Con el fin de tomar esta decisión,

se le pide que calcular  para cada una de las invitaciones  el número de maneras de llegar a la célula 

 (x_i, y_i) en el momento t_i.  Para cada invitación, supongamos que Max comienza a moverse de la celda (1, 1) en el momento 1.

Moverse entre dos celdas vecinas le lleva a Max exactamente una unidad de tiempo.  En particular, esto significa que Max puede entrar en la celda solo si un gato que estaba sentado en ella, la deja en el momento en que Max comienza su movimiento desde la celda vecina, y si ningún gato llega  a la celda en el momento en que Max está en ella. .

Dos formas de pasar de la celda (1, 1) a la celda (x,  y) en el tiempo t  se consideran distintas si, por lo menos durante un momento, de 1 a t  Las posiciones de Max son distintas para las dos formas en este momento.  Tenga en cuenta que durante este viaje Max puede visitar tanto (1, 1) como (x,  y) varias veces.  Como el número de formas puede ser bastante grande, imprímalo como módulo de 10⁹  + 7.

Input

La primera línea de la entrada contiene tres enteros positivos n, m y q    (1 ≤  n · m  ≤ 20, 1 ≤  q  ≤ 10000) - el número de filas y columnas en la tabla y el número de eventos, respectivamente.

Las siguientes líneas q describen los eventos, cada descripción contiene cuatro enteros tp_i, x_i, y_i y t_i (1 ≤  tp  ≤ 3, 1 ≤  x  ≤  n , 1 ≤  y  ≤  m , 2 ≤  t  ≤ 10⁹) - el tipo del evento (1 si Max recibe una invitación, 2 si un gato llega a la celda y 3 si un gato deja la celda), las coordenadas de la celda donde tiene lugar la acción y el momento en que la acción se lleva a cabo respectivamente.

Se garantiza que las consultas se dan en orden cronológico, es decir, t _i  <  t _{i  + 1}.

Output

Para cada invitación i (es decir,  tp_i  = 1), calcule el número de formas de llegar a la celda (x_i,  y_i) en el momento t_i.  Responda a las invitaciones cronológicamente, es decir, en el orden en que aparecen en la entrada.

Example

Input:
1 3 3
2 1 2 3
3 1 2 5
1 1 1 7

Output:
5