The evil owner Sasha kicked his cat Squirrel out onto the street. Now Squirrel needs to get back home. Sasha lives on the second floor of his palace. To reach him, Squirrel must go through $$$n$$$ steps. Initially, Squirrel is on step number $$$0$$$, and she needs to get to step number $$$n$$$. Squirrel is not very long, so the distance between any two of her paws must not exceed $$$2$$$. In one step, the cat moves one of her paws to the next step.
More formally, this means that at any moment for any positions of her paws $$$l_i$$$ and $$$l_j$$$, $$$|l_i - l_j| \le 2$$$.
Like any cat, Squirrel has different paws: left front, right front, left back, right back, and they are distinguishable. You need to help Squirrel count the number of ways to climb to step $$$n$$$. Two ways are considered different if at some step Squirrel moved different paws. Initially, all paws are on step number $$$0$$$.
Since the number of ways can be quite large, output it modulo $$$10^9 + 7$$$.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1\,000$$$) — the number of test cases.
In a single line of each test case, there is one integer $$$n$$$ ($$$1 \le n \le 1\,000\,000$$$) — the number of steps Squirrel needs to go through.
Note that there is no additional restriction on the sum of $$$n$$$ across all test cases.
For each test case, output one number — the number of ways to reach step $$$n$$$ modulo $$$10^9 + 7$$$.
3126
242520151698586
