# PROBLEM LINK:

* Author:* Ritik Gour

*Toshit Kale*

**Tester:***Ritik Gour*

**Editorialist:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

# PROBLEM:

Find the number of ways in which the stairstep of height N could be built using N rectangular blocks.

# QUICK EXPLANATION:

Find the n^{th} Catalan number using the formula and keep its value bounded to the maximum possible value of integer supported using modulo 10^9+7 in each step.

# EXPLANATION:

In the given problem, it was asked to find the number of ways in which the stairstep of height N could be built using N rectangular blocks.

Actually, this is one of the many applications of Catalan numbers.

The idea is to find the N^{th} Catalan number using the given formula.

Catalan numbers satisfy the following recursive formula:

C_0 = 1 and C_{n+1} = \sum_{i = 0}^{n} C_i C_{n-i}

Finding the value of the n^{th} Catalan number using the above-given formula requires exponential time.

So, a simple approach involving the direct use of the above-given formula would not be enough to satisfy the constraints for the given problem.

We can observe that the above recursive formula does a lot of repeated work. Since there are overlapping subproblems, we can use dynamic programming for this. The solution to this problem is a dynamic programming-based approach.

Firstly, an array is created to store the solutions of subsequent numbers starting from 0 up to the given number N.

The Catalan numbers for 0 and 1 are set to 1 and 1 respectively.

For numbers starting from 2 to N, the Catalan numbers are calculated using the already calculated values for previous numbers.

Since the answer could be a very large number (out of datatype bounds), modulo division is applied (mod 10^9+7) in each step of the calculation.

# SOLUTIONS:

## Setter's Solution

```
#include <iostream>
#define mod 1000000007
using namespace std;
unsigned long int stairWay(int n)
{
unsigned long int step[n + 1];
step[0] = step[1] = 1;
for (int i = 2; i <= n; i++) {
step[i] = 0;
for (int j = 0; j < i; j++)
step[i] = ((step[i] % mod) + ((step[j] % mod) * (step[i-j-1] % mod) % mod)) % mod;
}
return step[n];
}
int main()
{
int T,N;
cin>>T;
while(T--){
cin>>N;
cout<<stairWay(N)<<"\n";
}
return 0;
}
```

## Tester's Solution

```
#include <iostream>
#define mod 1000000007
using namespace std;
unsigned long int stairWay(int n)
{
unsigned long int step[n + 1];
step[0] = step[1] = 1;
for (int i = 2; i <= n; i++) {
step[i] = 0;
for (int j = 0; j < i; j++)
step[i] = ((step[i] % mod) + ((step[j] % mod) * (step[i-j-1] % mod) % mod)) % mod;
}
return step[n];
}
int main()
{
int T,N;
cin>>T;
while(T--){
cin>>N;
cout<<stairWay(N)<<"\n";
}
return 0;
}
```