The sequence of integer pairs (a1, b1), (a2, b2), ..., (ak, bk) is beautiful, if the following statements are fulfilled: 

  * 1 ≤ a1 ≤ b1 < a2 ≤ b2 < ... < ak ≤ bk ≤ n, where n is a given positive integer; 
  * all numbers b1 - a1, b2 - a2, ..., bk - ak are distinct. 



For the given number n find the number of beautiful sequences of length k. As the answer can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

Input

The first line contains integer t (1 ≤ t ≤ 2·105) — the number of the test data.

Each of the next t lines contains two integers n and k (1 ≤ k ≤ n ≤ 1000).

Output

For each test from the input print the answer to the problem modulo 1000000007 (109 + 7). Print the answers to the tests in the order in which the tests are given in the input.

Examples

Input

6
1 1
2 1
2 2
3 1
3 2
3 3


Output

1
3
0
6
2
0

Note

In the first test sample there is exactly one beautiful sequence: (1, 1).

In the second test sample, the following sequences are beautiful: 

  * (1, 1); 
  * (1, 2); 
  * (2, 2). 



In the fourth test sample, the following sequences are beautiful: 

  * (1, 1); 
  * (1, 2); 
  * (1, 3); 
  * (2, 2); 
  * (2, 3); 
  * (3, 3). 



In the fifth test sample, the following sequences are beautiful: 

  * (1, 1), (2, 3); 
  * (1, 2), (3, 3). 



In the third and sixth samples, there are no beautiful sequences.
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

/**
 * Created by hama_du on 2014/03/17.
 */
public class ProblemD {

    static final long MOD = 1000000007;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int t = in.nextInt();
        int[][] queries = new int[t][4];
        for (int i = 0 ; i < t ; i++) {
            queries[i][0] = i;
            queries[i][1] = in.nextInt();
            queries[i][2] = in.nextInt();
        }
        Arrays.sort(queries, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] ints2) {
                return ints[2] - ints2[2];
            }
        });

        int qh = 0;

        final int L = 46;
        long[][][][] dp = new long[2][2][1001][1001];
        for (int i = 0 ; i <= 1000 ; i++) {
            dp[0][0][0][i] = 1;
        }
        for (int i = 0 ; i < L*2 ; i++) {
            int fi = i%2;
            int ti = 1-fi;
            for (int j = 0 ; j <= 1000 ; j++) {
                for (int l = 1 ; l <= 1000 ; l++) {
                    for (int flg = 0 ; flg <= 1 ; flg++) {
                        if (dp[fi][flg][j][l] == 0) {
                            continue;
                        }
                        long base = dp[fi][flg][j][l];
                        if (i % 2 == 0) {
                            // a->b
                            int tl = l + j;
                            if (tl <= 1000 && j < 1000) {
                                dp[ti][0][j+1][tl] += base;
                                if (dp[ti][0][j+1][tl] >= MOD) {
                                    dp[ti][0][j+1][tl] -= MOD;
                                }
                            }
                            // a->a
                            if (j < 1000) {
                                dp[fi][0][j+1][l] += base;
                                if (dp[fi][0][j+1][l] >= MOD) {
                                    dp[fi][0][j+1][l] -= MOD;
                                }
                            }
                        } else {
                            if (l < 1000) {
                                // b -> a
                                dp[ti][0][j][l+1] += base;
                                if (dp[ti][0][j][l+1] >= MOD) {
                                    dp[ti][0][j][l+1] -= MOD;
                                }

                                // b -> b
                                dp[fi][1][j][l+1] += base;
                                if (dp[fi][1][j][l+1] >= MOD) {
                                    dp[fi][1][j][l+1] -= MOD;
                                }
                            }
                        }
                    }
                }
            }
            for (int flg = 0 ; flg <= 1 ; flg++) {
                for (int j = 0 ; j <= 1000 ; j++) {
                    Arrays.fill(dp[fi][flg][j], 0);
                }
            }

            if (i % 2 == 0) {
                int k = (i+2)/2;
                long[] sum = new long[1001];
                for (int j = 0 ; j <= 1000 ; j++) {
                    for (int l = 0 ; l <= 1000 ; l++) {
                        sum[l] += dp[ti][0][j][l];
                        if (sum[l] >= MOD) {
                            sum[l] -= MOD;
                        }
                    }
                }

                long fact = 1;
                for (int j = 1 ; j <= k ; j++) {
                    fact *= j;
                    fact %= MOD;
                }
                for (int l = 0 ; l <= 1000 ; l++) {
                    sum[l] *= fact;
                    sum[l] %= MOD;
                }
                for (int l = 2 ; l <= 1000 ; l++) {
                    sum[l] += sum[l-1];
                    sum[l] %= MOD;
                }
                while (qh < t) {
                    if (queries[qh][2] == k) {
                        queries[qh][3] = (int)(sum[queries[qh][1]]);
                    } else {
                        break;
                    }
                    qh++;
                }
            }
        }

        Arrays.sort(queries, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] ints2) {
                return ints[0] - ints2[0];
            }
        });

        for (int i = 0 ; i < t ; i++) {
            out.println(queries[i][3]);
        }
        out.flush();
    }

    public static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}
