Kelvin Climbs


Kelvin is facing a staircase problem. He lives in a mansion in which there are several staircases. He plays in his mansion and likes to climb each staircase 1,2 or, 3 steps at a time. When he plays, he wonders how many ways there are to reach the top of the staircase.

Determine the number of ways he can climb each staircase to solve the staircase problem, modulo 1010 + 7 on a new line. The heights for each of the staircases in his house are given.

It should recursively calculate and return the integer number of ways Kevin can climb the staircase, modulo 1010 + 7.

The purpose of this function is to solve the staircase problem.

Write a function solve which should have the following parameter(s):
1.) a = an integer which is the number of stairs in the staircase

Example
Input:
1
Output:
1

Explanation
The first staircase has only one step, so there is only one way to climb.

Input:
2
Output:
2

Explanation
The second staircase has two steps, so he can climb it in any two ways.
Input:
3
Output:
4

Explanation
The third staircase has three steps, so he can climb it any four ways.

Constraints
• The height of the staircase will be greater than or equal to 1 and less than or equal to 36.