SP7709 JZPCIR - Jumping Zippy

喜欢跳跃的 Zippy 每天都在进行跳跃活动，感到有些乏味。为了增加趣味性，他想出了一种新的跳跃方式。他在一个被分成 $n$ 个扇区的圆形广场上跳跃，这些扇区按照顺时针方向从 $0$ 到 $n-1$ 编号。Zippy 首先站在扇区 $0$ 上。每当他站在一个扇区 $x$ 时，他可以选择跳到以下扇区之一：$(x-2) \mod n$，$(x-1) \mod n$，$(x+1) \mod n$ 或 $(x+2) \mod n$。他的任务是跳遍所有扇区，且每个扇区只能访问一次，最后必须回到出发的扇区 $0$。另外，在第一次跳跃时，他不能跳到扇区 $n-1$ 或 $n-2$。现在，他想知道完成这一目标的不同方法有多少种。

第一行包含一个整数 $t$，表示测试用例的数量。（$1 \le t \le 1000$） 接下来的 $t$ 行中，每行给出一个整数 $n$，表示扇区的数量。（$5 \le n \le 10^{18}$）

对于每个测试用例，输出一行，表示 Zippy 完成目标的不同跳跃方式总数。由于结果可能非常大，只需输出对 $10^9 + 7$ 取模后的值。 **本翻译由 AI 自动生成**