Editing 3217 - Trepte 2.2

==Cerința==
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial se afla treapta 1)

==Date de intrare==
Programul citește de la tastatură numerele n și k.

==Date de ieșire==
Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.

==Restricții și precizări==
1 < n ≤ 1.000.000;
1 ≤ k ≤ n - 1;
deoarece numărul va fi prea mare sa va afișa modulo 9001;
la început, persoana se află pe treapta 1.
==Exemplul 1==:
Intrare

2 2
Ieșire

1
==Explicație==
Există o soluție, aceea când sare direct pe treapta 2.

==Exemplul 2==:
Intrare

4 2
Ieșire

3
==Explicație==
Prima: 1 -> 2 -> 3 -> 4
A doua: 1 -> 2 -> 4
A treia: 1 -> 3 -> 4
==Rezolvare==
def numar_moduri_urcare_trepte(n, k):
    mod = 9001

    # Inițializare vector dp
    dp = [0] * (n + 1)
    dp[1] = 1

    # Calcul numărul de moduri
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if i + j <= n:
                dp[i + j] = (dp[i + j] + dp[i]) % mod

    return dp[n]

# Citire date de intrare
n, k = map(int, input().split())

# Calcul și afișare rezultat
result = numar_moduri_urcare_trepte(n, k)
print(result)