Последовательность пар целых чисел (a1, b1), (a2, b2), ..., (ak, bk) называется красивой, если выполнены два условия:
Для заданного числа n найдите количество красивых последовательностей длины k. Так как ответ может быть достаточно большим, выведите его остаток от деления на 1000000007 (109 + 7).
В первой строке записано целое число t (1 ≤ t ≤ 2·105) — количество тестовых данных.
В каждой из следующих t строк содержатся два целых числа n и k (1 ≤ k ≤ n ≤ 1000).
Для каждого теста из входных данных выведите ответ на задачу по модулю 1000000007 (109 + 7). Ответы для тестов выводите в том порядке, в котором тесты заданы во входных данных.
В первом тестовом примере ровно одна красивая последовательность: (1, 1).
В втором тестовом примере следующие последовательности являются красивыми:
В четвертом тестовом примере следующие последовательности являются красивыми:
В пятом тестовом примере следующие последовательности являются красивыми:
В третьем и шестом тестовых примерах красивых последовательностей нет.
6 1 1 2 1 2 2 3 1 3 2 3 3
1 3 0 6 2 0
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач