Overview

Under the condition that you cannot land on broken steps, find the number of ways to climb from step \(0\) to step \(N\) by going “1/2/3 steps at a time”, modulo \(10^9+7\).

Analysis

Since you can advance at most 3 steps in a single move, the only possible positions you could have been at immediately before reaching step \(i\) are \(i-1, i-2, i-3\).
In other words, “the number of ways to reach step \(i\)” equals “the sum of the number of ways to reach steps \(i-1, i-2, i-3\)” (provided step \(i\) is not broken).

A naive recursive approach that “enumerates all possible climbing sequences” would branch 3 ways at each step, resulting in exponential time complexity, which is too slow for \(N \le 10^5\) (TLE).
Instead, we use dynamic programming (DP), where we compute and store the number of ways to reach each step exactly once, avoiding redundant recalculations.

Since broken steps “cannot be landed on”, we simply treat the number of ways to reach such steps as always \(0\) (jumping over them is OK).

Example: When \(N=5\) and the set of broken steps is \(\{2\}\)
- \(dp[0]=1\) (there is exactly 1 way to be on the ground) - \(dp[1]=dp[0]=1\) - \(dp[2]=0\) (broken, so landing is impossible) - \(dp[3]=dp[2]+dp[1]+dp[0]=0+1+1=2\) - \(dp[4]=dp[3]+dp[2]+dp[1]=2+0+1=3\) - \(dp[5]=dp[4]+dp[3]+dp[2]=3+2+0=5\)

Algorithm

Define \(dp[i]\) as “the number of ways to reach step \(i\)”.

• Initial value: \(dp[0]=1\)
• Transition:
  • If step \(i\) is broken, then \(dp[i]=0\)
  • Otherwise,
    \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\)
    (terms where \(i-2<0\) or \(i-3<0\) do not exist and are not added)
• Take each \(dp[i]\) modulo \(10^9+7\) as you go

Finally, output \(dp[N]\).

Complexity

• Time complexity: \(O(N + M)\) (registering broken steps is \(O(M)\), DP is \(O(N)\))
• Space complexity: \(O(N)\) (boolean array for broken status and DP array)

Implementation Notes

• To quickly determine whether a step is broken, prepare a boolean array broken of length \(N+1\).

• When \(M=0\), the second line of input may not exist, so it is safe to read all input at once using something like sys.stdin.read().split().

• Since the transition references at most 3 steps back, at the boundaries (\(i=1,2\)), only add the terms that exist.

• By always setting \(dp[i]=0\) for broken steps, paths that land on those steps are naturally excluded.

  Source Code

import sys

MOD = 10**9 + 7

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))

    broken = [False] * (N + 1)
    for _ in range(M):
        b = int(next(it))
        if 0 <= b <= N:
            broken[b] = True

    dp = [0] * (N + 1)
    dp[0] = 1

    for i in range(1, N + 1):
        if broken[i]:
            dp[i] = 0
        else:
            s = dp[i - 1]
            if i >= 2:
                s += dp[i - 2]
            if i >= 3:
                s += dp[i - 3]
            dp[i] = s % MOD

    print(dp[N] % MOD)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.