Đường đi và những chú mèo

Cho một bảng gồm $n$ hàng và $m$ cột. Ô ở hàng $r$, cột $c$ được ký hiệu là $(r,c)$. Một quân cờ xuất phát từ ô $(1,1)$ tại thời điểm $1$.

Tại mỗi đơn vị thời gian, từ ô $(r,c)$ quân cờ có thể di chuyển sang một trong bốn ô kề cạnh $(r-1,c)$, $(r+1,c)$, $(r,c-1)$, $(r,c+1)$ (nếu ô đó nằm trong bảng), hoặc đứng yên tại ô hiện tại. Mỗi lần di chuyển (hoặc đứng yên) mất đúng $1$ đơn vị thời gian.

Trên bảng có những con mèo xuất hiện và biến mất theo thời gian. Quân cờ không bao giờ được đứng trên ô có mèo. Cụ thể, quân cờ chỉ có thể bước vào một ô nếu con mèo (nếu có) trong ô đó rời đi đúng vào thời điểm quân cờ bắt đầu bước từ ô kề bên, và trong suốt thời gian quân cờ ở trong ô thì không có con mèo nào xuất hiện tại ô đó.

Có $q$ sự kiện, cho theo thứ tự thời gian tăng dần. Mỗi sự kiện có một trong ba dạng, kèm thời điểm $t$:

• $1xyt$: hỏi số cách để quân cờ đến được ô $(x,y)$ tại đúng thời điểm $t$. Đảm bảo tại thời điểm $t$ không có mèo trong ô $(x,y)$.
• $2xyt$: tại thời điểm $t$ một con mèo xuất hiện trong ô $(x,y)$. Đảm bảo trước đó không có mèo nào trong ô này.
• $3xyt$: tại thời điểm $t$ con mèo trong ô $(x,y)$ rời đi. Đảm bảo trước đó có mèo trong ô này.

Hai cách di chuyển được xem là khác nhau nếu tồn tại ít nhất một thời điểm trong khoảng từ $1$ đến $t$ mà vị trí quân cờ ở hai cách là khác nhau. Trong hành trình, quân cờ được phép đi qua ô $(1,1)$ và ô $(x,y)$ nhiều lần.

Với mỗi truy vấn dạng $1$, hãy in ra số cách tương ứng theo modulo ${10}^9+7$. Trả lời các truy vấn theo đúng thứ tự chúng xuất hiện.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $n$, $m$, $q$.
• $q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $tp$, $x$, $y$, $t$ mô tả một sự kiện.

Dữ liệu ra

Với mỗi truy vấn dạng $tp=1$, in ra trên một dòng số cách đến ô $(x,y)$ tại thời điểm $t$, theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n·m\le 20$
• $1\le q\le 10000$
• $1\le tp\le 3$, $1\le x\le n$, $1\le y\le m$, $2\le t\le {10}^9$
• Các sự kiện cho theo thứ tự thời gian tăng ngặt ($t_i<t_{i+1}$).

Ví dụ