Narrow Paths
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 2000
Tags: *special, combinatorics

Monocarp is wandering through a matrix consisting of $$$2$$$ rows and $$$n$$$ columns. Let's denote the cell in the $$$i$$$-th row and $$$j$$$-th column as $$$(i, j)$$$. Monocarp starts at cell $$$(1, 1)$$$ and wants to reach cell $$$(2, n)$$$.

In one move, Monocarp can move in one of two directions:

- right — from cell $$$(i, j)$$$ to cell $$$(i, j + 1)$$$;
- down — from cell $$$(i, j)$$$ to cell $$$(i + 1, j)$$$.

Monocarp can't go outside the matrix.

Polycarp wants to prevent Monocarp from freely wandering through the matrix. To do this, he wants to choose exactly $$$k$$$ different cells in the matrix and block them. He cannot choose cells $$$(1, 1)$$$ and $$$(2, n)$$$.

For each $$$i$$$ from $$$0$$$ to $$$n$$$, Polycarp wants to know how many ways he can block exactly $$$k$$$ cells, so that Monocarp has exactly $$$i$$$ different paths from $$$(1, 1)$$$ to $$$(2, n)$$$. Two paths are considered different if there exists a cell that Monocarp visits in one path but not in the other.

As the number of ways can be quite large, output it modulo $$$10^9 + 7$$$.

Input format:
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 2 \cdot n - 2$$$) — the number of columns in the matrix and the number of cells Polycarp wants to block.

Output format:
Output $$$n + 1$$$ integers: for each $$$i$$$ from $$$0$$$ to $$$n$$$, the number of ways to block exactly $$$k$$$ cells, so that Monocarp has exactly $$$i$$$ different paths from $$$(1, 1)$$$ to $$$(2, n)$$$. Output all answers modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 2

Example output:
1 0 0

Example input:
10 2

Example output:
45 24 21 18 15 12 9 6 3 0 0

Editorial:
If there are no blocked cells, then there are a total of $$$n$$$ different paths. Initially, Monocarp goes to the right, then descends in some column and goes all the way to the right. That is, the chosen column determines the path.
Now with blocked cells. Why might a path be inaccessible? Either Monocarp cannot go further to the right, or one of the cells in the column is blocked, or it cannot reach the end to the right. From this, the following conclusion can be drawn. In the first row, only the leftmost blocked cell is important, and in the second row, only the rightmost one is important.
If in the first row the leftmost blocked cell is at position $$$x$$$, and the rightmost in the second row is at position $$$y$$$, then Monocarp has access to $$$x - y + 1$$$ paths. We will deal with the case when there are no blocked cells in one of the rows later.
It can be noticed that the difference can be non-positive, but this simply means that there are $$$0$$$ paths. In practice, this case can be eliminated by calculating all the positive answers and subtracting them from the total number of ways to choose $$$k$$$ blocked cells out of $$$2n - 2$$$ options.
Let's say we have fixed $$$x - y = d$$$. Then the two fixed cells can be at positions $$$(d + 1, 1), (d + 2, 2), \dots, (n, n - d)$$$. In the case of $$$(d + 1, 1)$$$, the remaining $$$k - 2$$$ cells can be chosen from among $$$n - (d + 1)$$$ to the right of the first cell and among $$$0$$$ to the left of the second cell, totaling $$$n - (d + 1)$$$. In the case of $$$(d + 1, 1)$$$, this is $$$n - (d + 2)$$$ and $$$1$$$, again totaling $$$n - (d + 1)$$$. That is, with a fixed difference, we always have the same number of ways to choose the remaining $$$k - 2$$$ cells — $$$\binom{n - d - 1}{k - 2}$$$. And we know that the positions for the two cells can be chosen in $$$n - d$$$ ways. That is, the contribution to the answer for $$$d - 1$$$ is $$$\binom{n - d - 1}{k - 2} \cdot (n - d)$$$.
We still need to deal with the ways in which one of the rows has no blocked cells. Let's assume this is the case for the second row. Then the number of paths is still determined by the position of the leftmost blocked cell in the first row. Let's iterate over it and count the ways to arrange the remaining $$$k - 1$$$ cells. There are $$$\binom{n - i - 1}{k - 1}$$$ ways for the cell at position $$$i$$$.
If there are no blocked cells in the second row, then the answer is exactly the same. We iterate over the position of the rightmost cell and arrange the rest. It turns out to be symmetrical to the first method, so the formula is the same. We just calculate it once and multiply by $$$2$$$.
You can pre-calculate factorials to compute the binomial coefficient in $$$O(n + \log \textit{MOD})$$$.
Overall complexity: $$$O(n + \log \textit{MOD})$$$.