King's Move Paths

Given an (N\times N) grid, a king is initially placed at the top-left corner (cell ((1,1))). The king can move in three directions: right ((\rightarrow)), down ((\downarrow)), and diagonally right-down ((\searrow)). Your task is to compute the number of distinct paths the king can take to reach the bottom-right corner (cell ((N,N))) from the starting position. The movement can be described by the recurrence relation: [ dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], \quad \text{for } i,j > 1, ] with the base condition (dp[1][1] = 1).

Read a single integer (N) from standard input and output the number of distinct paths to standard output.

inputFormat

A single integer (N) representing the size of the grid is provided via standard input.

outputFormat

Output a single integer which is the number of distinct paths for the king to reach the bottom-right corner of the grid on standard output.## sample

1

1