Монокарп гуляет по матрице, состоящей из \(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\).
Выходные данные
Выведите \(n + 1\) целое число: для каждого \(i\) от \(0\) до \(n\) количество способов заблокировать ровно \(k\) клеток, чтобы у Монокарпа было ровно \(i\) различных путей из \((1, 1)\) в \((2, n)\). Все ответы выведите по модулю \(10^9 + 7\).