Problem Statement

Domino Tiling Queries You are given a family of `1 x 1 x 2` tile-arrangement queries. For every query value `n`, let `F(n)` be the number of valid arrangements for the corresponding `2 x n` floor, as defined by the following recurrence. `F(0) = 1`, `F(1) = 2`, and for every `n >= 2`: `F(n) = 4 * F(n - 1) + F(n - 2)`. Since the number of arrangements grows quickly, report every answer modulo `1000000007`. Input Format The first line contains an integer `q`, the number of queries. Each of the next `q` lines contains one integer `n`. Output Format For each query, print the number of valid tilings of a `2 x n` floor modulo `1000000007` on its own line. Example Input: `3` `1` `2` `3` Output: `2` `9` `32` For `n = 2`, the recurrence gives `4 * F(1) + F(0) = 9`. Constraints `1 <= q <= 100000` `1 <= n <= 1000000` Notes The source material supplies the initial values `F(1) = 2` and `F(2) = 9` but does not include enough arrangement-state detail to derive subsequent values. The re