{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" Saratov ACM ICPC teams have a tradition to come together on Halloween and recollect terrifying stories. And the most popular story among the newcomers is the story about the \"Mescher Tree\". A long time ago, when the famous Dmitry Mescheryakov aka Mescher was very young and he even didn\u0027t know how to write Dijkstra algorithm, he faced a difficult problem with a tree. Input file contained \u003ci\u003en\u003c/i\u003e\u0026nbsp;— the number of vertices, and pairs of vertices, connected with an edge. Without thinking a lot (honestly, the exact reason of that mistake is unknown), he wrote the following code:\u003cbr\u003e\u003cpre\u003e read(n);\u003cbr\u003e for i :\u003d 1 to n do begin\u003cbr\u003e read(u, v);\u003cbr\u003e g[u, v] :\u003d true;\u003cbr\u003e g[v, u] :\u003d true;\u003cbr\u003e end; \u003c/pre\u003e Mescher successfully compiled his code, got WA on sample test and started long debugging... This story has become a true legend. So it\u0027s no surprise that Saratov ACM ICPC teams use the following definition: connected undirected graph with \u003ci\u003en\u003c/i\u003e vertices and \u003ci\u003en\u003c/i\u003e edges is called \u003ci\u003e\u003cb\u003eMescheryakov Tree\u003c/b\u003e\u003c/i\u003e\u003cb\u003e or, less formally, \u003ci\u003e\u003cb\u003eMescher Tree\u003c/b\u003e\u003c/i\u003e\u003cb\u003e. The area of application of \u003ci\u003e\u003cb\u003eMescher trees\u003c/b\u003e\u003c/i\u003e is not well-studied, so we suggest you to solve one of the problems connected with such trees: given \u003ci\u003en\u003c/i\u003e, find the number of distinct \u003ci\u003e\u003cb\u003eMescher trees\u003c/b\u003e\u003c/i\u003e with \u003ci\u003en\u003c/i\u003e vertices. Trees are labeled, i.e. two trees are considered distinct if and only if their adjacency matrices differ.\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eInput contains single integer number \u003ci\u003en\u003c/i\u003e (3 ≤ \u003ci\u003en\u003c/i\u003e ≤ 5000).\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003eOutput the number of \u003ci\u003e\u003cb\u003eMescher trees\u003c/b\u003e\u003c/i\u003e with \u003ci\u003en\u003c/i\u003e vertices without leading zeroes.\u003cbr\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}