Задача . E. Странные вычисления и кошки

Мир Гоши является таблицей, состоящей из 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, x_i, y_i, t_i — Гошу зовут в гости в клетку (x_i, y_i) к моменту времени t_i. Гарантируется, что в клетке (x_i, y_i) нет в этот момент кошки.
• 2, x_i, y_i, t_i — в момент времени t_i в клетке (x_i, y_i) появляется кошка. Гарантируется, что в клетке (x_i, y_i) в этот момент не сидит другая кошка.
• 3, x_i, y_i, t_i — в момент времени t_i из клетки (x_i, y_i) уходит кошка. Гарантируется, что в этот момент в клетке (x_i, y_i) сидит кошка.

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

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

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

5

2
42

490902
10598759