题目描述

给定一个整数 $N$。Snuke 会选择整数 $s_1$，$s_2$，$n_1$，$n_2$，$u_1$，$u_2$，$k_1$，$k_2$，$e_1$ 和 $e_2$，以满足以下六个条件：

• $0 \\leq s_1 < s_2$
• $0 \\leq n_1 < n_2$
• $0 \\leq u_1 < u_2$
• $0 \\leq k_1 < k_2$
• $0 \\leq e_1 < e_2$
• $s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \\leq N$

对于每个可能的选择 $(s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1, e_2)$，计算 $(s_2 - s_1)(n_2 - n_1)(u_2 - u_1)(k_2 - k_1)(e_2 - e_1)$，并求所有计算值的和，结果取模 $(10^9 + 7)$。

解决给定的 $T$ 个测试用例中的每一个问题。

约束条件

• 输入中的所有值都是整数。
• $1 \\leq T \\leq 100$
• $1 \\leq N \\leq 10^9$

输入

从标准输入读入输入数据，输入格式如下：

$T$ $\\mathrm{case}_1$ $\\vdots$ $\\mathrm{case}_T$

每个测试用例的格式如下：

$N$

输出

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

示例输入1

4
4
6
10
1000000000

示例输出1

0
11
4598
257255556

• 当 $N=4$ 时，没有可能的选择 $(s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1, e_2)$。因此，答案为 $0$。
• 当 $N=6$ 时，有六个可能的选择 $(s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1, e_2)$，如下所示：
  • $(0,1,0,1,0,1,0,1,0,1)$
  • $(0,2,0,1,0,1,0,1,0,1)$
  • $(0,1,0,2,0,1,0,1,0,1)$
  • $(0,1,0,1,0,2,0,1,0,1)$
  • $(0,1,0,1,0,1,0,2,0,1)$
  • $(0,1,0,1,0,1,0,1,0,2)$
• 我们有一种选择，使得 $(s_2 - s_1)(n_2 - n_1)(u_2 - u_1)(k_2 - k_1)(e_2 - e_1)$ 为 $1$，有五种选择，使得 $(s_2 - s_1)(n_2 - n_1)(u_2 - u_1)(k_2 - k_1)(e_2 - e_1)$ 为 $2$，因此答案为 $11$。
• 请务必对结果取模 $(10^9 + 7)$。