Каваширо Нитори — девушка, которой нравится спортивное программирование. Однажды она нашла корневое дерево из \(n\) вершин. Корень дерева был в вершине с номером \(1\). Как продвинутый автор, она сразу придумала задачу.
У Каваширо Нитори есть множество вершин \(U=\{1,2,\ldots,n\}\). За одну операцию она будет выбирать множество вершин \(T\), где \(T\) является частичным виртуальным деревом множества \(U\), и заменять множество \(U\) на \(T\).
Множество вершин \(S_1\) называется частичным виртуальным деревом множества вершин \(S_2\), если \(S_1\) — подмножество \(S_2\), \(S_1 \neq S_2\) и для любых пар вершин \(i\) и \(j\) из \(S_1\) \(\operatorname{LCA}(i,j)\) лежит внутри \(S_1\), где \(\operatorname{LCA}(x,y)\) обозначает наименьшего общего предка вершин \(x\) и \(y\) в дереве. Обратите внимание, что множество вершин может иметь много различных частичных виртуальных деревьев.
Каваширо Нитори хочет узнать для каждого возможного \(k\), если применить операцию строго \(k\) раз, сколькими способами она может получить \(U=\{1\}\) в конце? Два способа считаются различными, если существует целое число \(z\) (\(1 \le z \le k\)) такое, что после \(z\) операций множества \(U\) различаются.
Так как ответ может быть большим, найдите его по модулю \(p\). Гарантируется, что \(p\) — простое число.
Выходные данные
Выведите единственную строку, состоящую из \(n-1\) целых чисел — ответ по модулю \(p\) для всех \(k=1,2,\ldots,n-1\).
Примечание
В первом примере при \(k=1\) единственный возможный способ следующий:
- \(\{1,2,3,4\} \to \{1\}\).
При \(k=2\) существуют \(6\) способов:
- \(\{1,2,3,4\} \to \{1,2\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,2,3\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,2,4\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,3\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,3,4\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,4\} \to \{1\}\).
При \(k=3\) существуют \(6\) возможных способов:
- \(\{1,2,3,4\} \to \{1,2,3\} \to \{1,2\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,2,3\} \to \{1,3\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,2,4\} \to \{1,2\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,2,4\} \to \{1,4\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,3,4\} \to \{1,3\} \to \{1\}\);
- \(\{1,2,3,4\} \to \{1,3,4\} \to \{1,4\} \to \{1\}\).