There are N seats in a row. N people come after each other to fill the seats according to the following rules:
We can verify that T(10) = 61632 and T(1 000) mod 100 000 007 = 47255094.
Find T(1 000 000) mod 100 000 007.
These problems are part of Project Euler and are licensed under CC BY-NC-SA 2.0 UK