Stepping on the Grid

Problem Background

Special for beginners, ^_^

Problem Description

There is a grid matrix whose boundary is at infinity. We make the following assumptions:

a. Each step, you may move from the current cell to one adjacent cell.

b. A visited cell collapses immediately and can never be stepped on again.

c. You may only move in three directions: north, east, and west.

Question: if you are allowed to take $n$ steps on the grid matrix, how many different paths are there? Two paths are considered different as long as they differ in any single step.

Input Format

The number of steps $n$ you are allowed to take on the grid ($n \le 20$).

Output Format

The number of paths computed.

Sample Input 1

2

Sample Output 1

7

Constraints

1s, 1024KiB for each test case.