Сознание Уилла связано с сознанием монстра с Обратной стороны, поэтому Уиллу известно все, о чем думает монстр. Неожиданно Уилл начал рисовать без остановок, страницу за страницей. Его мама Джойс и шериф Хоппер сложили все рисунки вместе и поняли, что это помеченное дерево!
Деревом называется связный ациклический граф. В дереве Уилла n вершин. Джойс и Хоппер не знают, что означает это дерево, поэтому они решили его исследовать, а также исследовать похожие деревья. Для каждого k такого, что 0 ≤ k ≤ n - 1, они собираются исследовать все такие помеченные деревья из n вершин, у которых ровно k ребер совпадают с ребрами дерева Уилла. Два помеченных дерева различны, если и только если существует пара вершин (v, u) такая, что в одном дереве существует ребро между вершинами v и u, а в другом — нет.
Хоппер и Джойс хотят узнать, сколько работы им предстоит, поэтому они просят вас посчитать для каждого k число помеченных деревьев из n вершин, у которых ровно k ребер совпадают с ребрами в дереве Уилла. Так как ответ может быть большим, выведите ответы по модулю 1000000007 = 109 + 7.
Выходные данные
Выведите n целых чисел на одной строке. i-е из этих чисел должно быть равно числу помеченных деревьев из n вершин таких, что ровно i - 1 ребро совпадает с ребрами в дереве Уилла, по модулю 1000 000 007 = 109 + 7.