Рассмотрим бинарные деревья, в которых у каждой вершины не более двух детей и каждая вершина помечена либо $$$0$$$, либо $$$1$$$.
За одну операцию можно инвертировать все метки на любом простом пути, проходящем через корень. Инвертировать метку означает заменить $$$0$$$ на $$$1$$$, а $$$1$$$ на $$$0$$$. Заметьте, что путь длины $$$1$$$, содержащий только корень, тоже разрешён.
Стоимость такого бинарного дерева определяется как минимальное число операций, необходимое для того, чтобы сделать все метки в дереве равными $$$0$$$.
Даны два целых числа $$$n$$$ и $$$k$$$. Посчитайте количество различных бинарных деревьев ровно с $$$n$$$ вершинами и стоимостью ровно $$$k$$$. Так как ответ может быть очень большим, выведите его по модулю $$$10^9 + 7$$$.
Два бинарных дерева считаются различными, если у них различается структура, либо если структура одинакова, но хотя бы в одной вершине различаются метки.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В единственной строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^6$$$, $$$0 \le k \le n$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите на отдельной строке одно целое число — количество помеченных бинарных деревьев с $$$n$$$ вершинами и стоимостью $$$k$$$ по модулю $$$10^9+7$$$.
62 02 11 17 669 67314159 42
2412016382216284559671824
В первом наборе входных данных имеем $$$n=2$$$ и $$$k=0$$$. Существует два возможных дерева — корень с левым ребёнком и корень с правым ребёнком. Поскольку нужна стоимость $$$0$$$, все вершины должны быть помечены $$$0$$$. Следовательно, ответ равен $$$2$$$.
Во втором наборе входных данных имеем $$$n=2$$$ и $$$k=1$$$. Таких деревьев $$$4$$$. Допустимые помеченные деревья показаны на рисунке ниже:
В третьем наборе входных данных имеем $$$n=1$$$ и $$$k=1$$$. Существует только одно дерево — одна корневая вершина с меткой $$$1$$$. Следовательно, ответ равен $$$1$$$.
