Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
51 - Andrew Stankevich's Contest, Warmup - 1004
Hexagon and Rhombic Dominoes

Time Limit: 5 Seconds      Memory Limit: 32768 KB

A regular hexagon with side length n is divided into 6n2 unit triangles.

Your task is to cover it with rhombic dominoes --- pieces composed of two unit triangles sharing a side.

Each domino must be placed in such a way, that it covers exactly two unit triangles. No triangle must be covered with more than one domino.

Count the number of ways to do so. For example there are two ways to cover a hexagon with side length~1, they are shown on the picture.

Input

Eace re several test cases in the input. Each case contains n (1 <= n <= 7 ). There is an empty line between each case.

Output

Output the number of ways to cover hexagon with rombic dominoes. There should be an empty line between each case.

Example

InputOutput
12
220

Submit    Status