| 问题描述 |
|---|
国际象棋中，骑士可以以 $$3 \times 2$$ 的日字形进行攻击。 如果在 $$k \times k$$ 的棋盘上放置两个骑士，使得这两个骑士不会互相攻击，有多少种放置方案？
|
| 输入描述 |
多组案例，第一行是一个正整数 $$T$$ 表示案例的个数。（$$1 \le T \le 10^5$$） 每组案例只有一行，是一个正整数 $$k$$ 。（$$1 \le k \le 10^9$$）
|
| 输出描述 |
每组案例输出一行，输出 $$k \times k$$ 的放置方案。
结果可能很大，输出对 $$1000000007$$ 取模后的答案。 |
| 样例输入复制样例 |
1 8 |
| 样例输出 |
1848 |
| 相关 |