| Codeforces Round 329 (Div. 2) |
|---|
| Закончено |
Мир Гоши является таблицей, состоящей из 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) до клетки (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.
