Description

There is an infinite grid matrix. We make the following assumptions:
a. Each step can only move from the current cell to an adjacent cell;
b. Once a cell is stepped on, it immediately collapses and cannot be stepped on again;
c. Movement is only allowed in the north, east, and west directions.

The question is: Given that you are allowed to take n steps on the grid matrix, how many distinct paths are possible? Two paths are considered different if they differ in at least one step.

Input Format

The number of allowed steps n (where n ≤ 20).

Output Format

The calculated number of distinct paths.

2

7