4546：和平骑士

国际象棋中，骑士可以以 $$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

题单#15（加法&乘法&容斥原理、组合计数）