Eight Princes

Time limit8sMemory limit512 MB

Summary

Count the ways to seat eight distinct princes on N round-table seats so that no two occupy adjacent seats or opposite seats (opposite only when N is even).

Level: Hard8 of 10
Topics: Combinatorics, Math, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

In a kingdom far away there lived eight princes. They got along badly, so a quarrel started every time two of them met.

One day a party was held and all eight princes had to sit at the same round table. Their mood never improved, so a quarrel breaks out whenever one of these happens.

A prince takes the seat next to another prince.
A prince takes the seat directly opposite another prince, because the two then trade nasty looks. This can happen only when the table has an even number of seats.

Each prince's seat therefore has to be chosen with care. Given the number of seats on the table, count the ways to seat all eight princes in peace.

Input

The input has several lines. Each line holds one integer $N$ , the number of seats on the round table. A line holding a single 0 ends the input.

Every $N$ satisfies $1 \le N \le 66$ .

Output

For each $N$ , print on its own line the number of ways to seat all eight princes without a quarrel. Rotated and mirrored placements count as different. The princes are distinct, so seating different princes on the same set of seats also counts as different.

The answer never exceeds $10^{14}$ .

Examples4

Example 1
Input
```
8
16
17
0
```
Expected output
```
0
0
685440
```
Example 2
Input
```
1
2
5
15
0
```
Expected output
```
0
0
0
0
```

Example 3

Input

Expected output

Example 4

Input

Expected output