Staircase Climbing: Counting Ways without Three Consecutive Steps

You are given an integer n which represents the number of stairs in a staircase. At each step, you have the option to climb either 1, 2, or 3 stairs at a time. Your task is to calculate the number of distinct ways to reach the top of the staircase. Since the number of ways can be very large, you should output the result modulo \(10^9+7\).

The recurrence relation for the number of ways is given by:

[ dp[n] = dp[n-1] + dp[n-2] + dp[n-3] ]

with the base cases defined as:

• \(dp[1] = 1\)
• \(dp[2] = 2\)
• \(dp[3] = 4\)

For example:

• For \(n = 1\), the answer is 1.
• For \(n = 3\), the answer is 4.
• For \(n = 4\), since \(dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7\), the answer is 7.
• For \(n = 6\), the answer is 24.

inputFormat

The input consists of a single integer n on a single line, representing the number of stairs.

Example Input:
3

outputFormat

Output a single integer representing the number of distinct ways to climb to the top of the staircase modulo \(10^9+7\).

Example Output:
4

## sample

1

1

</p>