#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
#define sqr(x) ((x) * (x))
#define ll long long
#define SZ(X) ((int) ((X).size()))
using namespace std;
const ll MOD = 1e9 + 7;
int sz;
struct Matrix {
ll x[22][22];
void print() {
REP(i,sz) {
REP(j,sz) cout << x[i][j] << ' '; cout << endl;
}
cout << endl;
}
} A, I;
struct Vector {
ll x[22];
void print() {
PR0(x, sz);
}
} f;
Vector update(const Vector& f, const Matrix& A) {
Vector res;
REP(i,sz) {
res.x[i] = 0;
REP(j,sz)
res.x[i] = (res.x[i] + A.x[i][j] * f.x[j]) % MOD;
}
return res;
}
Matrix operator * (const Matrix& a, const Matrix& b) {
Matrix res;
REP(i,sz) REP(j,sz) {
res.x[i][j] = 0;
REP(k,sz)
res.x[i][j] = (res.x[i][j] + a.x[i][k] * b.x[k][j]) % MOD;
}
return res;
}
Matrix power(const Matrix& a, int k) {
if (k == 0) return I;
if (k == 1) return a;
Matrix mid = power(a, k >> 1);
mid = mid * mid;
if (k & 1) return mid * a;
return mid;
}
const int MN = 22;
int m, n, q, id[MN][MN];
const int di[5] = {-1,1,0,0,0};
const int dj[5] = {0,0,-1,1,0};
bool outside(int u, int v) {
return u < 1 || v < 1 || u > m || v > n;
}
void init() {
int cur = 0;
FOR(i,1,m) FOR(j,1,n) id[i][j] = cur++;
memset(I.x, 0, sizeof I.x);
memset(A.x, 0, sizeof A.x);
sz = m * n;
REP(i,sz) I.x[i][i] = 1;
FOR(i,1,m) FOR(j,1,n) {
REP(dir,5) {
int ii = i + di[dir], jj = j + dj[dir];
if (outside(ii, jj)) continue;
A.x[ id[i][j] ][ id[ii][jj] ] = 1;
}
}
}
int main() {
ios :: sync_with_stdio(false);
{
n = 5; m = 4; q = 10000;
init();
memset(f.x, 0, sizeof f.x);
f.x[0] = 1;
int cur_time = 1;
for(int i = 0; i < q; i++) {
int typ = 1;
int x = 1, y = 1, t = i * 1000 + 10;
// update until time moment t-1
Matrix up = power(A, t - 1 - cur_time);
f = update(f, up);
if (typ == 2) {
// cannot go to cell (x, y)
REP(dir,5) {
int xx = x + di[dir], yy = y + dj[dir];
if (outside(xx, yy)) continue;
A.x[ id[x][y] ][ id[xx][yy] ] = 0;
}
}
f = update(f, A);
if (typ == 1) {
cout << (int) f.x[id[x][y]] << '\n';
}
cur_time = t;
if (typ == 3) {
// can now go to cell (x, y)
REP(dir,5) {
int xx = x + di[dir], yy = y + dj[dir];
if (outside(xx, yy)) continue;
A.x[ id[x][y] ][ id[xx][yy] ] = 1;
}
}
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIEZPUihpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk8PV9iOyBpKyspCiNkZWZpbmUgRk9SRChpLGEsYikgZm9yKGludCBpPShhKSxfYj0oYik7IGk+PV9iOyBpLS0pCiNkZWZpbmUgUkVQKGksYSkgZm9yKGludCBpPTAsX2E9KGEpOyBpPF9hOyBpKyspCiNkZWZpbmUgRUFDSChpdCxhKSBmb3IoX190eXBlb2YoYS5iZWdpbigpKSBpdCA9IGEuYmVnaW4oKTsgaXQgIT0gYS5lbmQoKTsgKytpdCkKCiNkZWZpbmUgREVCVUcoeCkgeyBjb3V0IDw8ICN4IDw8ICIgPSAiOyBjb3V0IDw8ICh4KSA8PCBlbmRsOyB9CiNkZWZpbmUgUFIoYSxuKSB7IGNvdXQgPDwgI2EgPDwgIiA9ICI7IEZPUihfLDEsbikgY291dCA8PCBhW19dIDw8ICcgJzsgY291dCA8PCBlbmRsOyB9CiNkZWZpbmUgUFIwKGEsbikgeyBjb3V0IDw8ICNhIDw8ICIgPSAiOyBSRVAoXyxuKSBjb3V0IDw8IGFbX10gPDwgJyAnOyBjb3V0IDw8IGVuZGw7IH0KCiNkZWZpbmUgc3FyKHgpICgoeCkgKiAoeCkpCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgU1ooWCkgKChpbnQpICgoWCkuc2l6ZSgpKSkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGxsIE1PRCA9IDFlOSArIDc7CgppbnQgc3o7CnN0cnVjdCBNYXRyaXggewogICAgbGwgeFsyMl1bMjJdOwoKICAgIHZvaWQgcHJpbnQoKSB7CiAgICAgICAgUkVQKGksc3opIHsKICAgICAgICAgICAgUkVQKGosc3opIGNvdXQgPDwgeFtpXVtqXSA8PCAnICc7IGNvdXQgPDwgZW5kbDsKICAgICAgICB9CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9IEEsIEk7CgpzdHJ1Y3QgVmVjdG9yIHsKICAgIGxsIHhbMjJdOwoKICAgIHZvaWQgcHJpbnQoKSB7CiAgICAgICAgUFIwKHgsIHN6KTsKICAgIH0KfSBmOwoKVmVjdG9yIHVwZGF0ZShjb25zdCBWZWN0b3ImIGYsIGNvbnN0IE1hdHJpeCYgQSkgewogICAgVmVjdG9yIHJlczsKICAgIFJFUChpLHN6KSB7CiAgICAgICAgcmVzLnhbaV0gPSAwOwogICAgICAgIFJFUChqLHN6KQogICAgICAgICAgICByZXMueFtpXSA9IChyZXMueFtpXSArIEEueFtpXVtqXSAqIGYueFtqXSkgJSBNT0Q7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgpNYXRyaXggb3BlcmF0b3IgKiAoY29uc3QgTWF0cml4JiBhLCBjb25zdCBNYXRyaXgmIGIpIHsKICAgIE1hdHJpeCByZXM7CiAgICBSRVAoaSxzeikgUkVQKGosc3opIHsKICAgICAgICByZXMueFtpXVtqXSA9IDA7CiAgICAgICAgUkVQKGssc3opCiAgICAgICAgICAgIHJlcy54W2ldW2pdID0gKHJlcy54W2ldW2pdICsgYS54W2ldW2tdICogYi54W2tdW2pdKSAlIE1PRDsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KCk1hdHJpeCBwb3dlcihjb25zdCBNYXRyaXgmIGEsIGludCBrKSB7CiAgICBpZiAoayA9PSAwKSByZXR1cm4gSTsKICAgIGlmIChrID09IDEpIHJldHVybiBhOwoKICAgIE1hdHJpeCBtaWQgPSBwb3dlcihhLCBrID4+IDEpOwogICAgbWlkID0gbWlkICogbWlkOwoKICAgIGlmIChrICYgMSkgcmV0dXJuIG1pZCAqIGE7CiAgICByZXR1cm4gbWlkOwp9Cgpjb25zdCBpbnQgTU4gPSAyMjsKaW50IG0sIG4sIHEsIGlkW01OXVtNTl07Cgpjb25zdCBpbnQgZGlbNV0gPSB7LTEsMSwwLDAsMH07CmNvbnN0IGludCBkals1XSA9IHswLDAsLTEsMSwwfTsKCmJvb2wgb3V0c2lkZShpbnQgdSwgaW50IHYpIHsKICAgIHJldHVybiB1IDwgMSB8fCB2IDwgMSB8fCB1ID4gbSB8fCB2ID4gbjsKfQoKdm9pZCBpbml0KCkgewogICAgaW50IGN1ciA9IDA7CiAgICBGT1IoaSwxLG0pIEZPUihqLDEsbikgaWRbaV1bal0gPSBjdXIrKzsKCiAgICBtZW1zZXQoSS54LCAwLCBzaXplb2YgSS54KTsKICAgIG1lbXNldChBLngsIDAsIHNpemVvZiBBLngpOwoKICAgIHN6ID0gbSAqIG47CiAgICBSRVAoaSxzeikgSS54W2ldW2ldID0gMTsKCiAgICBGT1IoaSwxLG0pIEZPUihqLDEsbikgewogICAgICAgIFJFUChkaXIsNSkgewogICAgICAgICAgICBpbnQgaWkgPSBpICsgZGlbZGlyXSwgamogPSBqICsgZGpbZGlyXTsKICAgICAgICAgICAgaWYgKG91dHNpZGUoaWksIGpqKSkgY29udGludWU7CgogICAgICAgICAgICBBLnhbIGlkW2ldW2pdIF1bIGlkW2lpXVtqal0gXSA9IDE7CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGlvcyA6OiBzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgIHsKCQluID0gNTsgbSA9IDQ7IHEgPSAxMDAwMDsKICAgICAgICBpbml0KCk7CgogICAgICAgIG1lbXNldChmLngsIDAsIHNpemVvZiBmLngpOwogICAgICAgIGYueFswXSA9IDE7CgogICAgICAgIGludCBjdXJfdGltZSA9IDE7CgogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBxOyBpKyspIHsKICAgICAgICAgICAgaW50IHR5cCA9IDE7CiAgICAgICAgICAgIGludCB4ID0gMSwgeSA9IDEsIHQgPSBpICogMTAwMCArIDEwOwoKICAgICAgICAgICAgLy8gdXBkYXRlIHVudGlsIHRpbWUgbW9tZW50IHQtMQogICAgICAgICAgICBNYXRyaXggdXAgPSBwb3dlcihBLCB0IC0gMSAtIGN1cl90aW1lKTsKICAgICAgICAgICAgZiA9IHVwZGF0ZShmLCB1cCk7CgogICAgICAgICAgICBpZiAodHlwID09IDIpIHsKICAgICAgICAgICAgICAgIC8vIGNhbm5vdCBnbyB0byBjZWxsICh4LCB5KQogICAgICAgICAgICAgICAgUkVQKGRpciw1KSB7CiAgICAgICAgICAgICAgICAgICAgaW50IHh4ID0geCArIGRpW2Rpcl0sIHl5ID0geSArIGRqW2Rpcl07CiAgICAgICAgICAgICAgICAgICAgaWYgKG91dHNpZGUoeHgsIHl5KSkgY29udGludWU7CgogICAgICAgICAgICAgICAgICAgIEEueFsgaWRbeF1beV0gXVsgaWRbeHhdW3l5XSBdID0gMDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmID0gdXBkYXRlKGYsIEEpOwoKICAgICAgICAgICAgaWYgKHR5cCA9PSAxKSB7CiAgICAgICAgICAgICAgICBjb3V0IDw8IChpbnQpIGYueFtpZFt4XVt5XV0gPDwgJ1xuJzsKICAgICAgICAgICAgfQogICAgICAgICAgICBjdXJfdGltZSA9IHQ7CgogICAgICAgICAgICBpZiAodHlwID09IDMpIHsKICAgICAgICAgICAgICAgIC8vIGNhbiBub3cgZ28gdG8gY2VsbCAoeCwgeSkKICAgICAgICAgICAgICAgIFJFUChkaXIsNSkgewogICAgICAgICAgICAgICAgICAgIGludCB4eCA9IHggKyBkaVtkaXJdLCB5eSA9IHkgKyBkaltkaXJdOwogICAgICAgICAgICAgICAgICAgIGlmIChvdXRzaWRlKHh4LCB5eSkpIGNvbnRpbnVlOwoKICAgICAgICAgICAgICAgICAgICBBLnhbIGlkW3hdW3ldIF1bIGlkW3h4XVt5eV0gXSA9IDE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0=