D. Красивые пары чисел
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Последовательность пар целых чисел (a1, b1), (a2, b2), ..., (ak, bk) называется красивой, если выполнены два условия:

  • 1 ≤ a1 ≤ b1 < a2 ≤ b2 < ... < ak ≤ bk ≤ n, где n — заданное целое положительное число;
  • все числа b1 - a1, b2 - a2, ..., bk - ak различные.

Для заданного числа n найдите количество красивых последовательностей длины k. Так как ответ может быть достаточно большим, выведите его остаток от деления на 1000000007 (109 + 7).

Входные данные

В первой строке записано целое число t (1 ≤ t ≤  2·105) — количество тестовых данных.

В каждой из следующих t строк содержатся два целых числа n и k (1 ≤ k ≤ n ≤ 1000).

Выходные данные

Для каждого теста из входных данных выведите ответ на задачу по модулю 1000000007 (109 + 7). Ответы для тестов выводите в том порядке, в котором тесты заданы во входных данных.

Примеры
Входные данные
6
1 1
2 1
2 2
3 1
3 2
3 3
Выходные данные
1
3
0
6
2
0
Примечание

В первом тестовом примере ровно одна красивая последовательность: (1, 1).

В втором тестовом примере следующие последовательности являются красивыми:

  • (1, 1);
  • (1, 2);
  • (2, 2).

В четвертом тестовом примере следующие последовательности являются красивыми:

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

В пятом тестовом примере следующие последовательности являются красивыми:

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

В третьем и шестом тестовых примерах красивых последовательностей нет.