Strange Calculation and Cats

Gosha's universe is a table consisting of n rows and m columns. Both the rows and columns are numbered with consecutive integers starting with 1. We will use (r, c) to denote a cell located in the row r and column c.

Gosha is often invited somewhere. Every time he gets an invitation, he first calculates the number of ways to get to this place, and only then he goes. Gosha's house is located in the cell (1, 1).

At any moment of time, Gosha moves from the cell he is currently located in to a cell adjacent to it (two cells are adjacent if they share a common side). Of course, the movement is possible only if such a cell exists, i.e. Gosha will not go beyond the boundaries of the table. Thus, from the cell (r, c) he is able to make a move to one of the cells (r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1). Also, Ghosha can skip a move and stay in the current cell (r, c).

Besides the love of strange calculations, Gosha is allergic to cats, so he never goes to the cell that has a cat in it. Gosha knows exactly where and when he will be invited and the schedule of cats travelling along the table. Formally, he has q records, the i-th of them has one of the following forms:

• 1, x_i, y_i, t_i — Gosha is invited to come to cell (x_i, y_i) at the moment of time t_i. It is guaranteed that there is no cat inside cell (x_i, y_i) at this moment of time.
• 2, x_i, y_i, t_i — at the moment t_i a cat appears in cell (x_i, y_i). It is guaranteed that no other cat is located in this cell (x_i, y_i) at that moment of time.
• 3, x_i, y_i, t_i — at the moment t_i a cat leaves cell (x_i, y_i). It is guaranteed that there is cat located in the cell (x_i, y_i).

Gosha plans to accept only one invitation, but he has not yet decided, which particular one. In order to make this decision, he asks you to calculate for each of the invitations i the number of ways to get to the cell (x_i, y_i) at the moment t_i. For every invitation, assume that Gosha he starts moving from cell (1, 1) at the moment 1.

Moving between two neighboring cells takes Gosha exactly one unit of tim. In particular, this means that Gosha can come into the cell only if a cat sitting in it leaves the moment when Gosha begins his movement from the neighboring cell, and if none of the cats comes to the cell at the time when Gosha is in it.

Two ways to go from cell (1, 1) to cell (x, y) at time t are considered distinct if for at least one moment of time from 1 to t Gosha's positions are distinct for the two ways at this moment. Note, that during this travel Gosha is allowed to visit both (1, 1) and (x, y) multiple times. Since the number of ways can be quite large, print it modulo 10⁹ + 7.