Time limit per test: 0.5 second(s) Memory limit: 65536 kilobytes
input: standard output: standard
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't know how to write Dijkstra algorithm, he faced a difficult problem with a tree. Input file contained n — 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:
read(n); for i := 1 to n do begin read(u, v); g[u, v] := true; g[v, u] := true; end;
Mescher successfully compiled his code, got WA on sample test and started long debugging... This story has become a true legend. So it's no surprise that Saratov ACM ICPC teams use the following definition: connected undirected graph with n vertices and n edges is called Mescheryakov Tree or, less formally, Mescher Tree. The area of application of Mescher trees is not well-studied, so we suggest you to solve one of the problems connected with such trees: given n, find the number of distinct Mescher trees with n vertices. Trees are labeled, i.e. two trees are considered distinct if and only if their adjacency matrices differ.
Input
Input contains single integer number n (3 ≤ n ≤ 5000).
Output
Output the number of Mescher trees with n vertices without leading zeroes.