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.

Example(s)

sample input	sample output
3	1