Monkey Friendship Brawl

In a forest there are initially \(N\) little monkeys that do not know each other. They frequently get into fights; however, the two monkeys involved in a fight must not be good friends at that moment. After each fight, not only do the two fighting monkeys become friends, but so do all of their good friends with each other. After exactly \(N-1\) fights, all the monkeys become good friends.

Your task is to count the total number of different fight processes that can lead to this outcome.

It can be shown that the final answer is given by the formula:

[ F(N)=N^{N-2}\times (N-1)!]

For example, when \(N=3\), there are 6 different processes:

• Fight sequence: {1-2, 1-3}
• Fight sequence: {1-2, 2-3}
• Fight sequence: {1-3, 1-2}
• Fight sequence: {1-3, 2-3}
• Fight sequence: {2-3, 1-2}
• Fight sequence: {2-3, 1-3}

Note that during each fight, if the two groups of monkeys that are about to merge have sizes \(a\) and \(b\) respectively, then there are exactly \(a\times b\) choices for selecting the actual pair to fight. The final answer is the product of all such choices over the entire process.

inputFormat

The input consists of a single integer \(N\) \( (1 \leq N \leq \text{small})\) representing the number of monkeys in the forest.

outputFormat

Output a single number, the total number of different fight processes. That is, output \(F(N)=N^{N-2}\times (N-1)!\).

sample

2

1