Non‐Crossing Hamiltonian Path Count

Given n points in the plane (with n ≥ 3), consider connecting these points with straight line segments one after another to form a single continuous path that visits every point exactly once. The condition is that no two segments should cross each other. It can be proved that when n = 3 there is exactly 1 way to do so, and when n = 4 there are at most 3 such ways. Given n, write a program to compute the total number of ways to connect the points under the above condition.

One way to solve the problem is to show that the answer for n points is given by the difference of two consecutive Catalan numbers, i.e., \[ f(n)=C_{n-1}-C_{n-2}, \] where the Catalan numbers \( C_m \) are defined by \[ C_m = \frac{1}{m+1}\binom{2m}{m}. \] For example, when n = 3, we have \[ C_2 - C_1 = 2 - 1 = 1,\] and when n = 4, \[ C_3 - C_2 = 5 - 2 = 3.\] This formulation will yield the correct answers for all valid inputs.

inputFormat

The input consists of a single integer n (n ≥ 3), representing the number of points.

outputFormat

Output a single integer representing the number of ways to connect the points as described.

sample

3

1