Замостить полосу

Полосу размером $2 \times n$ клеток замащивают костяшками домино $1 \times 2$, которые можно класть и вдоль, и поперёк.

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

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

Одно число.

Посмотрите на самый левый столбец: он либо закрыт вертикальной костяшкой, либо парой горизонтальных вместе со следующим столбцом. Других вариантов нет.