Question
Diagonal Tally Path Enumeration
Given an n × n grid with the top-left corner indexed as (0, 0), a Diag Tally is defined as a staircase walk from the bottom-left corner (n−1, 0) to the top-right corner (0, n−1) while remaining above the diagonal cells (or cells on the line from the bottom-left to the top-right). The task is to enumerate the number of Diag Tally paths from (n−1, 0) to (0, n−1).
Note:
Staircase walk: A walk that only allows upward or rightward movements, resembling the steps of a staircase.
Diagonal cells: The cells that lie along the line from the bottom-left corner to the top-right corner of the grid.
Note:
Staircase walk: A walk that only allows upward or rightward movements, resembling the steps of a staircase.
Diagonal cells: The cells that lie along the line from the bottom-left corner to the top-right corner of the grid.
Input
The first and only line of the input contains a single integer n, denoting the dimension of the grid.
Constraints
1 ≤ N ≤ 30
Constraints
1 ≤ N ≤ 30
Output
Print the number of Diag Tally paths from (n−1, 0) to (0, n−1).
Note: The answer can we very large, so use appropriate datatype.
Note: The answer can we very large, so use appropriate datatype.
Example
Sample Input
2
Sample Output
2
Explanation
As here in the image, we can see that there are 2 available options of going from bottom-left to top-right.
2
Sample Output
2
Explanation
As here in the image, we can see that there are 2 available options of going from bottom-left to top-right.