Кузнечик

Кузнечик сидит на нулевой ступени лестницы и прыгает вверх на одну или на две ступени за раз.

Сколькими способами он может добраться до ступени с номером $n$? Ответ выведите по модулю $10^9 + 7$.

Одно целое число $n$ от $0$ до $10^6$.

Одно число.

На ступень $i$ кузнечик попадает либо с $i-1$, либо с $i-2$, и эти способы не пересекаются. Значит количество способов на $i$ — сумма количеств на двух предыдущих. Хранить весь массив не нужно: хватает двух переменных.