Kotlin Heroes: Episode 10 |
---|
Закончено |
Монокарп гуляет по матрице, состоящей из $$$2$$$ строк и $$$n$$$ столбцов. Будем обозначать клетку в $$$i$$$-й строке в $$$j$$$-м столбце $$$(i, j)$$$. Монокарп начинает в клетке $$$(1, 1)$$$ и хочет прийти в клетку $$$(2, n)$$$.
За один ход Монокарп может перейти в одном из двух направлений:
Монокарп не может выходить за границы матрицы.
Поликарп хочет помешать Монокарпу свободно гулять по матрице. Для этого он хочет выбрать ровно $$$k$$$ различных клеток в матрице и заблокировать их. Он не может выбирать клетки $$$(1, 1)$$$ и $$$(2, n)$$$.
Для каждого $$$i$$$ от $$$0$$$ до $$$n$$$ Поликарп хочет знать, сколько способов заблокировать ровно $$$k$$$ клеток у него есть, чтобы у Монокарпа было ровно $$$i$$$ различных путей из $$$(1, 1)$$$ в $$$(2, n)$$$. Два пути считаются различными, если существует такая клетка, которую Монокарп посещает в одном пути, но не в другом.
Так как число способов может быть достаточно большим, выведите его по модулю $$$10^9 + 7$$$.
В единственной строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 2 \cdot n - 2$$$) — количество столбцов матрицы и количество клеток, которые хочет заблокировать Поликарп.
Выведите $$$n + 1$$$ целое число: для каждого $$$i$$$ от $$$0$$$ до $$$n$$$ количество способов заблокировать ровно $$$k$$$ клеток, чтобы у Монокарпа было ровно $$$i$$$ различных путей из $$$(1, 1)$$$ в $$$(2, n)$$$. Все ответы выведите по модулю $$$10^9 + 7$$$.
2 2
1 0 0
10 2
45 24 21 18 15 12 9 6 3 0 0
10 5
7812 420 210 90 30 6 0 0 0 0 0
22 10
467563090 1847560 1016158 534820 267410 125840 55055 22022 7865 2420 605 110 11 0 0 0 0 0 0 0 0 0 0
Название |
---|