题目描述

有一个小球，他的初始位置在 \((0,0,0)\)。

接下来 \(k\) 分钟，每一分钟它都会进行一次移动。

每次移动依次执行：

1. 向上或向下移动 \(1\) 距离。

2. 向左或向右移动 \(1\) 距离。

3. 向前或向后移动 \(1\) 距离。

求最后小球仍在 \((0,0,0)\) 的概率 \(\times 10^{9}\) 并向下取整的值。

输入格式

本题采用多组数据。

第一行，一个数 \(T\)，代表数据组数。

接下来 \(T\) 行，每行一个数，代表 \(k\)。

输出格式

共 \(T\) 行。

对于每组数据。一行，输出一个数，代表答案。

样例 #1

样例输入 #1

4
2
5
10000
100000000000

样例输出 #1

125000000
0
507
0

提示

本题采用测试点捆绑。

数据范围：

Subtask #0 （10分）：\(T=1,1 \le k \le 10\)。

Subtask #1 （45分）：\(1 \le T \le 10^5,1 \le k \le 10^7\)。

Subtask #2 （30分）：\(1 \le T \le 10^5,1 \le k \le 10^{18}\)。

Subtask #3 （15分）：\(1 \le T \le 10^5,1 \le k \le 10^{18}\)，保证 \(k\) 是奇数。