Монокарп гуляет по матрице, состоящей из $$$2$$$ строк и $$$n$$$ столбцов. Будем обозначать клетку в $$$i$$$-й строке в $$$j$$$-м столбце $$$(i, j)$$$. Монокарп начинает в клетке $$$(1, 1)$$$ и хочет прийти в клетку $$$(2, n)$$$.

За один ход Монокарп может перейти в одном из двух направлений:

• направо — из клетки $$$(i, j)$$$ в клетку $$$(i, j + 1)$$$;
• вниз — из клетки $$$(i, j)$$$ в клетку $$$(i + 1, j)$$$.

Монокарп не может выходить за границы матрицы.

Поликарп хочет помешать Монокарпу свободно гулять по матрице. Для этого он хочет выбрать ровно $$$k$$$ различных клеток в матрице и заблокировать их. Он не может выбирать клетки $$$(1, 1)$$$ и $$$(2, n)$$$.

Для каждого $$$i$$$ от $$$0$$$ до $$$n$$$ Поликарп хочет знать, сколько способов заблокировать ровно $$$k$$$ клеток у него есть, чтобы у Монокарпа было ровно $$$i$$$ различных путей из $$$(1, 1)$$$ в $$$(2, n)$$$. Два пути считаются различными, если существует такая клетка, которую Монокарп посещает в одном пути, но не в другом.

Так как число способов может быть достаточно большим, выведите его по модулю $$$10^9 + 7$$$.