E. Странные вычисления и кошки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мир Гоши является таблицей, состоящей из n строк и m столбцов. И строки и столбцы нумеруются последовательными целыми числами, начиная с единицы. Будем обозначать как (r, c) клетку, расположенную в строке с номером r и столбце с номером c.

Гошу часто зовут в гости. Каждый раз, когда его зовут он сначала считает количество способов дойти до того места и лишь потом идет. Дом Гоши расположен в клетке (1, 1).

В каждый момент времени Гоша переходит из текущей клетки в клетку соседнюю с ней по ребру, если такая клетка конечно существует, то есть Гоша не выйдет за границы таблички. Таким образом, из клетки (r, c) совершается ход в одну из клеток (r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1). Гоша может пропустить перемещение и остаться в текущей клетке.

Помимо любви к странным вычислениям, Гоша страдает аллергией на кошек, поэтому никогда не пойдёт в клетку, в которой сидит кошка. Гоша знает, в какое время его позовут в гости, и расписание перемещения котов по таблице. У него есть q записей, i-я из которых выглядит одним из следующих способов:

  • 1, xi, yi, ti — Гошу зовут в гости в клетку (xi, yi) к моменту времени ti. Гарантируется, что в клетке (xi, yi) нет в этот момент кошки.
  • 2, xi, yi, ti — в момент времени ti в клетке (xi, yi) появляется кошка. Гарантируется, что в клетке (xi, yi) в этот момент не сидит другая кошка.
  • 3, xi, yi, ti — в момент времени ti из клетки (xi, yi) уходит кошка. Гарантируется, что в этот момент в клетке (xi, yi) сидит кошка.
Гоша планирует воспользоваться только одним приглашением в гости, но пока не решил каким именно, поэтому просит вас вычислить для каждого из приглашений количество способов дойти в нужную клетку к нужному моменту времени, если он начнёт идти из клетки (1, 1) в момент времени один.

На перемещение между двумя соседними клетками у Гоши уходит ровно один момент времени. В частности это означает, что Гоша может прийти в клетку, только если сидящий в ней кот уходит в момент, предшествующий тому, когда Гоша начинает своё движение из соседней клетки, и если ни один кот не придёт в клетку в момент времени, когда в ней окажется Гоша.

Два способа дойти из клетки (1, 1) до клетки (x, y) в момент времени t считаются различными, если хотя бы для одного момента времени от единицы до t позиции Гоши в этот момент отличаются в двух способах. Обратите внимание, что во время данного путешествия Гоша может заходить как в клетку (1, 1) так и в клетку (x, y) произвольное количество раз. Так как число способов может быть довольно большое, выведите его по модулю 109 + 7

Входные данные

В первой строке входных данных записаны три целых положительных числа n, m и q (1 ≤ n·m ≤ 20, 1 ≤ q ≤ 10 000) — количество строк и столбцов в таблице, а так же количество событий соответственно.

Следующие q строк описывают события, каждое описание содержит четыре целых числа tpi, xi, yi и ti (1 ≤ tp ≤ 3, 1 ≤ x ≤ n, 1 ≤ y ≤ m, 2 ≤ t ≤ 109) — тип события (1 когда Гошу зовут в гости, 2 когда появляется кошка и 3 когда кошка уходит), координаты клетки, с которой происходит действие, момент времени, в которое происходит действие соответственно.

Гарантируется, что запросы даны в хронологическом порядке, то есть ti < ti + 1.

Выходные данные

Для каждого приглашения в гости i (то есть tpi = 1) выведите количество способов попасть в клетку клетку (xi, yi) в момент времени ti. Отвечайте на приглашения в хронологическом порядке, то есть в порядке их следования во входном файле.

Примеры
Входные данные
1 3 3
2 1 2 3
3 1 2 5
1 1 1 7
Выходные данные
5
Входные данные
3 3 3
2 2 2 2
1 3 3 5
1 3 3 7
Выходные данные
2
42
Входные данные
4 5 5
2 2 5 3
2 2 4 6
3 2 4 9
1 4 4 13
1 4 4 15
Выходные данные
490902
10598759
Примечание

Пояснение к первому примеру. В каждой картинке указано количество способов прийти в клетку в соответствующий момент времени. (X обозначает заблокированную клетку в этот момент)

Момент времени 1.
Момент времени 2.
Момент времени 3.
Момент времени 4.
Момент времени 5.
Момент времени 6.
Момент времени 7.