Злой хозяин Саша выгнал свою кошку Белку на улицу. Теперь Белке нужно обратно попасть домой. Саша живет на втором этаже своего дворца. Чтобы к нему попасть, нужно пройти через $$$n$$$ ступенек. Изначально Белка стоит на ступеньке с номером $$$0$$$, и ей нужно попасть на ступеньку номер $$$n$$$. Белка не очень длинная, поэтому, расстояние между любыми двумя ее лапками должно быть не больше $$$2$$$. За один шаг кошка переносит одну из своих лапок на следующую ступеньку.
Более формально это значит, что в каждый момент для любых позиций ее лапок $$$l_i$$$ и $$$l_j$$$, $$$|l_i - l_j| \le 2$$$.
Как у любой кошки, у Белки разные лапки: левая передняя, правая передняя, левая задняя, правая задняя, и они различимы. Вам нужно помочь Белке посчитать количество способов подняться на ступеньку $$$n$$$. Два способа являются различными, если на каком-то шаге Белка переставила разные лапки. Изначально все лапки находятся на ступеньке с номером $$$0$$$.
Так как количество способов может быть достаточно большим, выведите его по модулю $$$10^9 + 7$$$.
В первой строке дано одно целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество тестовых наборов.
В единственной строке каждого набора данных дано одно целое число $$$n$$$ ($$$1 \le n \le 1\,000\,000$$$) — количество ступенек, через которые нужно пройти Белке.
Обратите внимание, что нет дополнительного ограничения на сумму $$$n$$$ по всем наборам входных данных.
Для каждого набора выведите одно число — количество вариантов добраться до ступеньки $$$n$$$ по модулю $$$10^9 + 7$$$.
3126
242520151698586
