481. Hero of Our Time

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:

for i := 1 to n do begin
read(u, v);
g[u, v] := true;
g[v, u] := true;
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 contains single integer number n (3 ≤ n ≤ 5000).

Output the number of Mescher trees with n vertices without leading zeroes.

sample input
sample output