Каваширо Нитори — девушка, которой нравится спортивное программирование. Однажды она нашла корневое дерево из $$$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$$$ — простое число.