SP13626 CBANK - Charu and Coin Distribution

Charu 有一天去银行存入他的零花钱，但他面临一个问题：他希望存入正好 $N$ 卢比。他拥有面值为 $0.25$、$0.50$、$1.0$ 和 $2.0$ 卢比的硬币，每种硬币的数量都是 $4 \times N$ 个。他想知道，使用这些硬币，正好存入 $N$ 卢比的方法有多少种。由于 Charu 不擅长计数，他希望能得到你的帮助。现在给定一个输入数字 $N$，请计算出用这些硬币恰好存入 $N$ 卢比的所有可能方案的数量，并输出该数量对 $1000000007$ 取模的结果，这是因为数量可能会非常大。

第一行是一个整数 $t$，表示测试用例的数量。 接下来的 $t$ 行，每行都有一个整数 $N$。 满足 $1 \leq t \leq 10000$ 且 $1 \leq N \leq 10^9$。

对于每个测试用例，输出一行结果，表示在对应情况下问题的解。 **本翻译由 AI 自动生成**