# Davis Staircase Problem in Java

Davis has several stairs in his home and prefers to ascend one, two, or three steps at a time. As a highly clever youngster, he thinks about how many ways it can reach the top of the staircase.

Considering R the heights of each of his house's stairs, calculate and display the total number of ways he may climb every staircase, module 1010 +7 on a new line.

Example

P= 5

This staircase comprises five steps. Davis may take the steps listed below in the following order:

``````1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3
3 2
``````

There are 13 possible outcomes for these five steps, and 13 modulo 10000000007 = 13.

### Explanation of the Function

Within the editor below, replace the stepPerms function utilizing recursion.

The following parameters are available in stepPerms:

int P: number of stairs in the staircase

### Returns

int: total number of ways Davis may climb the stairs modulo 10000000007

### Format of Input

The first line includes a single integer, R, that signifies the number of staircases inside his home.

Each of the R lines that follows has a single integer, P, representing the height of staircase u.

### Constraints

1 ≤ R ≤ 5

1 ≤  P ≤ 36

1 ≤  P ≤ 20 for the 50% highest possible score.

### Input Sample

``````STDIN      Function
-----           --------
3               R = 3 (number of staircases)
1               first staircase P = 1
3               second P = 3
7               third P = 7
``````

Output Sample

``````1
4
44
``````

Explanation

Let us count the total number of approaches to ascend the first two Davis's=3 staircases:

1. Since the first staircase only has a P=1 step, there is just one method by which he can ascend it (i.e., by jumping 1 step). As a result, we display 1 on a new line.
2. This second staircase contains P=3 stairs, and he may ascend it in one of four ways:
``````1  →  1  →  1
1  →  2
2  →  1
3
``````

As a result, we print 4 on a new line.

Filename: DavisStaircase.java

``````import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class DavisStaircase {
public static class Matrix{
static int P;
public   Matrix(int P)
{
this.P=P;
}
static long[][] multiply(long[][] x ,long[][] y)
{
long[][] ans=new long[P][P];
for(int u=0;u<P;u++)
for(int v=0;v<P;v++){
ans[u][v]=0;
for(int w=0;w<P;w++)
ans[u][v]+=x[u][w]*y[w][v];
}
return ans;
}
static void print(long[][] x)
{
for(int u=0;u<P;u++)
{
for(int v=0;v<P;v++)
System.out.print(x[u][v]+" ");
System.out.println();
}
}
//Matrix Exponentiation
static long MatrixExpo(long[][] base ,int power )
{
// print(base);
//base cases
if(power<=0) return 0;
if(power==1) return 1;
if(power==2) return 2;
if(power==3) return 4;
power-=3;
long[][] ans=new long[P][P];
for(int u=1;u<P;u++)
for(int v=0;v<P;v++)  ans[u][v]=0;
ans=4;ans=2;ans=1;
//Left-handside matrix
//4 2 1
//0 0 0
//0 0 0
while(power>0)
{
if(power%2==1)
ans=multiply(ans ,base);
power=power/2;
base=multiply(base ,base);
}
return ans;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int R = in.nextInt();
long[][] Q=new long;
//1 1 0
//1 0 1
//1 0 0
Q=Q=Q=1;Q=1;Q=0;
Q=0;Q=1;Q=0;Q=0;
for(int x0 = 0; x0 < R; x0++){
int P = in.nextInt();
Matrix mat= new Matrix(3);
System.out.println(Matrix.MatrixExpo(Q ,P));
}
}
}
``````

Input

``````3
1
3
7
``````

Output

``````1
4
44
``````

Filename: DavisStaircase.java

``````import java.util.*;
public class DavisStaircase {
public static int numWays(int P) {
if (P < 3) {
return P;
}
if (P == 3) {
return 4;
}
int[] numWays = new int[P];
numWays = 1; //finding the number of ways.
numWays = 2; //finding the number of ways.
numWays = 4; //finding the number of ways.
for (int u = 3; u < P; u++) {
numWays[u] = numWays[u - 1] + numWays[u - 2] + numWays[u - 3];
}
return numWays[P - 1];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int P = in.nextInt();  // initializing the value.
while (in.hasNext()) { // checking the while condition.
int staircaseHeight = in.nextInt();
System.out.println(numWays(staircaseHeight));
}
}
}
``````

Input

``````2
5
8
``````

Output

``````13
81
``````