Counting Ways to Climb Stairs

You are given a staircase with N steps. Your task is to determine the number of distinct ways to climb to the top if you can take 1, 2, or 3 steps at a time. Since the result can be huge, output the answer modulo \(10^9+7\).

For example, if N = 4, the possible ways to climb the stairs are:

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 2 + 2
• 1 + 3
• 3 + 1

Thus, the answer for N = 4 is 7.

inputFormat

The input consists of a single integer N (0 ≤ N ≤ 10⁵), representing the number of stairs.

outputFormat

Output a single integer, which is the number of distinct ways to climb the stairs modulo \(10^9+7\).

4

7