Big changes

The Far Far Away Kingdom has n cities. The king wants to connect the cities with n - 1 two-way airline so that:

• Each airline connects two different cities.

• From each city it is possible to get to any other city directly or with transfers.

We will call the accessibility of a city the number of cities with which it is directly connected by airlines. The king also requires that the maximum value of accessibility among all the cities of the kingdom be as large as possible.

How many different ways exists to connect cities as required?

Input

One integer n (2 ≤ n ≤ 10^9) - the number of cities.

Output

Print one integer - the answer to the problem.

Examples

Note

The maximum possible value of accessibility for three cities is 2. Three different connection are possible where this value is achieved: (1,2) and (2,3), (1,3) and (2,3), (1,2) and (1,3).