Big Changes

Time limit2sMemory limit512 MB

Summary

On N labeled cities, count the spanning trees whose maximum degree is as large as possible, i.e. the star trees.

Level: Medium5 of 10
Topics: Combinatorics, Tree, Math, Graph
Solved: No attempts yet

Problem

The kingdom of Far Far Away has $N$ cities. The king wants to connect the cities with $N-1$ bidirectional airlines so that:

Each airline connects two distinct cities.
From any city, one can reach any other city directly or with transfers.

Let the accessibility of a city be the number of cities directly connected to it by airlines. The king also requires that the maximum accessibility among all cities of the kingdom be as large as possible.

How many distinct ways are there to connect the cities in the required manner?

Input

The input contains a single integer $N$ , the number of cities ( $2 \le N \le 10^9$ ).

Output

Output a single integer, the answer to the problem.

Hint

Let us explain the example. The maximum possible accessibility for three cities is 2. There are three distinct ways to connect them that achieve it: (1,2)(2,3), (1,3)(2,3), (1,2)(1,3).

Examples1

Example 1
Input
```
3
```
Expected output
```
3
```