#include <bits/stdc++.h>
// #include <atcoder/all>
// using namespace atcoder;
using namespace std;
// #define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef double ld;
typedef pair<ld, ld> LDP;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
// 1->close(c), 0->open(o)
#define r11(i, l, r) for (int i = (l); i <= (r); ++i)
#define p11(i, l, r) for (int i = (r); i >= (l); --i)
#define r10(i, l, r) for (int i = (l); i < (r); ++i)
#define p10(i, l, r) for (int i = (r)-1; i >= (l); --i)
// #define r01(i, l, r) for (int i = (l) + 1; i <= (r); ++i)
// #define p01(i, l, r) for (int i = (r); i > (l); --i)
#define r1n(i, n) r11(i, 1, n)
#define r0n(i, n) r10(i, 0, n)
#define p1n(i, n) p11(i, 1, n)
#define p0n(i, n) p10(i, 0, n)
#define FOR(i, s, e, step) for (int i = s; i <= e; i += step)
#define fora(i, v) for (auto i : (v))
#define fori(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define all(v) (v).begin(), (v).end()
#define all_(v, n) (v) + 1, (v) + (n) + 1
const ld eps = 1e-10;
const ld pi = acosl(-1.0);
const ll mod = 1e9 + 7;
template <typename T>
void chmin(T& a, T b) {
    a = min(a, b);
}
template <typename T>
void chmax(T& a, T b) {
    a = max(a, b);
}

// mod should be <2^31
struct modint {
    int n;
    modint() : n(0) { ; }
    modint(ll m) {
        if (m < 0 || mod <= m) {
            m %= mod;
            if (m < 0) m += mod;
        }
        n = m;
    }
    operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint operator+=(modint& a, modint b) {
    a.n += b.n;
    if (a.n >= mod) a.n -= (int)mod;
    return a;
}
modint operator-=(modint& a, modint b) {
    a.n -= b.n;
    if (a.n < 0) a.n += (int)mod;
    return a;
}
modint operator*=(modint& a, modint b) {
    a.n = ((ll)a.n * b.n) % mod;
    return a;
}
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
    if (n == 0) return modint(1);
    modint res = (a * a) ^ (n / 2);
    if (n % 2) res = res * a;
    return res;
}

ll inv(ll a, ll p) { return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p); }
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) {
    a = a / b;
    return a;
}

/*
A001100
Let T{n, k} = number of permutations of 12...n with exactly k rising or falling successions. 
Let S[n](t) = Sum_{k >= 0} T{n, k}*t^k. Then S[0] = 1; S[1] = 1; S[2] = 2*t; S[3] = 4*t+2*t^2; 
for n >= 4, S[n] = (n+1-t)*S[n-1] - (1-t)*(n-2+3*t)*S[n-2] - (1-t)^2*(n-5+t)*S[n-3] + (1-t)^3*(n-3)*S[n-4].
S[n] = (n+1-t)*S[n-1] - ((-3*t^2)+(5-n)*t+n-2)*S[n-2] - (t^3+(n-7)*t^2+(11-2*n)*t+n-5)*S[n-3] + ((3-n)*t^3+(3*n-9)*t^2+(9-3*n)*t+n-3)*S[n-4]
*/
modint T[2010][2010];
void init(int n) {
    T[0][0] = 1;
    T[1][0] = 1;
    T[2][1] = 2;
    T[3][1] = 4;
    T[3][2] = 2;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            modint k = T[i][j];
#define n (i + 1)
            if (n >= 4) T[n][j] += (modint)(n + 1) * k, T[n][j + 1] += -k;
#undef n
#define n (i + 2)
            if (n >= 4)
                T[n][j + 2] -= (modint)-3 * k,
                    T[n][j + 1] -= (modint)(5 - n) * k,
                    T[n][j] -= (modint)(n - 2) * k;
#undef n
#define n (i + 3)
            if (n >= 4)
                T[n][j + 3] -= k, T[n][j + 2] -= (modint)(n - 7) * k,
                    T[n][j + 1] -= (modint)(11 - 2 * n) * k,
                    T[n][j] -= (modint)(n - 5) * k;
#undef n
#define n (i + 4)
            if (n >= 4)
                T[n][j + 3] += (modint)(3 - n) * k,
                    T[n][j + 2] += (modint)(3 * n - 9) * k,
                    T[n][j + 1] += (modint)(9 - 3 * n) * k,
                    T[n][j] += (modint)(n - 3) * k;
#undef n
        }
    }
    // for (int i = 1; i <= 10; i++) {
    //     for (int j = 0; j <= 10; j++) {
    //         cerr << T[i][j] << " ";
    //     }
    //     cerr << endl;
    // }
}
#define MULTIPLE_TEST_CASES 1
inline void _sol() {
    int n, m;
    cin >> n >> m;
    cout << T[n][m] << '\n';
}
// signed main() {
int main() {
    // freopen(".in", "r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    init(2000);
#ifdef MULTIPLE_TEST_CASES
    int t;
    cin >> t;
    while (t--) {
        _sol();
    }
#else
    _sol();
#endif
    return 0;
}