# Count Ways To Reach The N-th Stairs

#### You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair. Each time you can either climb one step or two steps. You are supposed to return the number of distinct ways in which you can climb from the 0th step to Nth step.

##### Example :

```
N=3
```

```
We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.
```

#### Input format :

```
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow.
The first and the only argument of each test case contains an integer 'N', representing the number of stairs.
```

##### Output format :

```
For each test case/query, print the number of distinct ways to reach the top of stairs. Since the number can be huge, so return output modulo 10^9+7.
Output for every test case will be printed in a separate line.
```

##### Note :

```
You do not need to print anything. It has already been taken care of.
```

##### Constraints :

```
1 <= T <= 100
0 <= N <= 10^18
Where 'T' is the number of test cases, and 'N' is the number of stairs.
```

One basic approach is to explore all possible steps which can be climbed with either taking one step or two steps. So at every step, we have two options to climb the stairs either we can climb with one step, or we can climb with two steps. So the number of ways can be recursively defined as :

`countDistinctWayToClimbStair ( currStep, N ) = countDistinctWayToClimbStair ( currStep+1, N ) + countDistinctWayToClimbStair ( currStep + 2, N )`

Where “currStep” denotes the current step on which the person is standing, and N denotes the destination step.

In the previous approach, we were naively calculating the results for every step. So there were lots of redundant calls because if we look at the recursion tree, then there are only ‘N’ distinct function calls. So we should avoid redundant function calling. For that, we decide to store the result at each step, and we will directly return the result for that step whenever a function is called again for those steps. We will be storing the result into “dp”.

Where dp[currStep] defines the number of distinct ways to climb the stairs from “currStep” to ‘N’-th steps.

## Note :

**Since N can be 10^18 so even if you will be creating the array of integers then also it'll give the memory limit to exceed.**

As we have seen that this problem can be broken into subproblems. And many subproblems were the same, so for that; we were using memoization. So instead of storing the result through recursion, we are going to store the result iteratively. Our intuition is:

How can we reach “currStep” step in taking one step or two steps:

- We can take the one-step from (currStep-1)th step or,
- We can take the two steps from (currStep-2)th step.

So the total number of ways to reach “currStep” will be the sum of the total number of ways to reach at (currStep-1)th and the total number of ways to reach (currStep-2)th step.

Let dp[currStep] define the total number of ways to reach “currStep” from the 0th. So,

`dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]`

The base case will be, If we have 0 stairs to climb then the number of distinct ways to climb will be one (we are already at Nth stair that’s the way) and if we have only one stair to climb then the number of distinct ways to climb will be one, i.e. one step from the beginning.

## Note :

**Since N can be 10^18 so even if you will be creating the array of integers then also it'll give the memory limit to exceed.**

In the previous approach, we were using “dp” which took O(N) space. But there was no need of taking a space of O(N). Because if we look at any step of dp:

` dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]`

We only need the answer of the two-step and the one-step before the “currStep” for evaluation of the “currStep”. So we can replace “dp” with two variables let’s say “oneStep” and “twoSteps”. Where “oneStep” denotes the total number of ways to reach (currStep-1)th step from beginning and “twoSteps” denotes the total number of ways to reach (currStep-2)th step from the beginning. So,

` currStep=oneStep+twoStep`

So the above statement is (N-1)th Fibonacci Number. We can calculate the ‘N’th Fibonacci Number using Binary Matrix Exponentiation explained below. Here, Fn represents the nth Fibonacci number. We will raise the matrix to the power of (n - 1) so that the top-left element gives the value of F(n + 1 - 1) = F(n).

[[1 1] (pow n) [[(F(n+1) F(n)]

[1 0]] = [ F(n) F(n-1)]]

- So we need to find the (N - 1)th Power of this Matrix.
- We can write a function for the multiplication of two matrices.
- Then we can use binary exponentiation to calculate the ‘N’ power of this Matrix in log(N).
- Binary Exponentiation / Fast Exponentiation:

```
long long binpow(Matrix a, long long b) {
if (b == 0)
return 1;
Matrix res = binpow(a, b / 2);
if (b % 2)
return res * res * a;
else
return res * res;
}
```

- Similarly, we can write a version for Matrix Exponentiation.
- Take care of overflow using modulo by 10^9 + 7 at each operation of Matrix Multiplication.