Convex Permutomino#4163
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 () is convex, whereas the one in image () is not.
A polyomino is defined as a permutomino if it comprises 2 \cdot n vertices, all of which have coordinates ranging from to . Additionally, it must not have two vertical segments sharing the same -coordinate or two horizontal segments sharing the same -coordinate. The image below shows a permutomino with vertices, which is also convex.
Given the number , your task is to determine the number of distinct convex permutominoes with 2 \cdot n vertices. Two permutominoes are considered identical if they can be perfectly aligned with each other, without allowing for rotations or reflections.
The input consists of a single integer (2 \leq n \leq 30).
Output a single integer representing the number of convex permutominoes with 2 \cdot n vertices.
Example 1
Ensure that you only count convex permutominoes.
