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

Последовательность пар целых чисел (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).

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