Convex Permutomino

A polyomino is a connected set of cells on a grid. A polyomino is termed convex if every row and every column within it is connected. For instance, the polyomino depicted in image (a) is convex, whereas the one in image (b) is not.

A polyomino is defined as a permutomino if it comprises 2·n vertices, all of which have coordinates ranging from 1 to n. Additionally, it must not have two vertical segments sharing the same x-coordinate or two horizontal segments sharing the same y-coordinate. The image below shows a permutomino with 14 vertices, which is also convex.

Given the number n, your task is to determine the number of distinct convex permutominoes with 2·n vertices. Two permutominoes are considered identical if they can be perfectly aligned with each other, without allowing for rotations or reflections.

Input

The input consists of a single integer n (2 ≤ n ≤ 30).

Output

Output a single integer representing the number of convex permutominoes with 2·n vertices.

Examples

Note

Ensure that you only count convex permutominoes.