cho.sh

Eight Princes

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).

Hard8CombinatoricsMathDynamic programmingBit manipulationNo attempts yetTime limit8sMemory limit512 MB

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 NN, the number of seats on the round table. A line holding a single 0 ends the input.

Every NN satisfies 1≤N≤661 \le N \le 66.

Output

For each NN, 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 101410^{14}.