Placement of Keys

Time limit1sMemory limit128 MB

Summary

Count the key placements that open all boxes after forcing open the first two, for each n up to 200.

Level: Medium6 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

There are $n$ boxes $A_1, A_2, \dots, A_n$ with $3 \le n \le 200$ , and every box has its own lock. No two locks are alike. Put the $n$ keys that open these locks into the $n$ boxes, one key per box, then lock every box.

Now force open $A_1$ and $A_2$ and take out the keys inside. If one of those keys opens a locked box, open it and take out the key inside to unlock another box. Repeat until no further box can be opened.

If all $n$ boxes end up open, the arrangement of the keys is called a good placement. How many different good placements are there?

Input

The input holds several data, one integer $n$ per line. The last line holds $-1$ , which marks the end of the input and is not a datum.

Output

For each datum print two lines. The first line is N=, then the given $n$ , then a colon. The second line is the number of good placements.

Examples1

Example 1
Input
```
6
8
-1
```
Expected output
```
N=6:
240
N=8:
10080
```