Сломанные ступени

Кузнечик прыгает на одну или две ступени, начиная с нулевой. Некоторые ступени сломаны, вставать на них нельзя.

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

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n + 1$ число, по одному на ступени с нулевой по $n$-ю: 1 — ступень цела, 0 — сломана.

Одно число.

Сломанная ступень — состояние, в которое нельзя попасть. Оставьте у неё ноль способов, и всё остальное посчитается само.