ограничение по времени на тест 2 секунды ограничен...

ограничение по времени на тест 2 секунды
ограничение по памяти на тест 256 мегабайт
Рассмотрим бинарные деревья, в которых у каждой вершины не более двух детей и каждая вершина помечена либо 0, либо 1.

За одну операцию можно инвертировать все метки на любом простом пути, проходящем через корень. Инвертировать метку означает заменить 0 на 1, а 1 на 0. Заметьте, что путь длины 1, содержащий только корень, тоже разрешён.

Стоимость такого бинарного дерева определяется как минимальное число операций, необходимое для того, чтобы сделать все метки в дереве равными 0.

Даны два целых числа 𝑛 и 𝑘. Посчитайте количество различных бинарных деревьев ровно с 𝑛 вершинами и стоимостью ровно 𝑘. Так как ответ может быть очень большим, выведите его по модулю 10^9+7.

Два бинарных дерева считаются различными, если у них различается структура, либо если структура одинакова, но хотя бы в одной вершине различаются метки.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число 𝑡 (1≤𝑡≤10^4) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора входных данных содержатся два целых числа 𝑛 и 𝑘 (1≤𝑛≤10^6, 0≤𝑘≤𝑛).

Гарантируется, что сумма значений 𝑛 по всем наборам входных данных не превосходит 10^6.

Выходные данные
Для каждого набора входных данных выведите на отдельной строке одно целое число — количество помеченных бинарных деревьев с 𝑛 вершинами и стоимостью 𝑘 по модулю 10^9+7.

Пример
входные данныеСкопировать
6
2 0
2 1
1 1
7 6
69 67
314159 42
выходные данныеСкопировать
2
4
1
2016
382216284
559671824
Примечание
В первом наборе входных данных имеем 𝑛=2 и 𝑘=0. Существует два возможных дерева — корень с левым ребёнком и корень с правым ребёнком. Поскольку нужна стоимость 0, все вершины должны быть помечены 0. Следовательно, ответ равен 2.

Во втором наборе входных данных имеем 𝑛=2 и 𝑘=1. Таких деревьев 4. Допустимые помеченные деревья показаны на рисунке ниже:

В третьем наборе входных данных имеем 𝑛=1 и 𝑘=1. Существует только одно дерево — одна корневая вершина с меткой 1. Следовательно, ответ равен 1.

Реши на с++