### 问题描述 你是一个资深程序员，今天去某著名互联网公司参加面试。一进门，面试官就给了你一个大活儿：“我们公司有一个内部系统，由 $n$ 台服务器组成，这 $n$ 台服务器的编号分别为 $1\sim n$，且每两台服务器之间都通过一条双向传输的网线连接。最近系统频繁出现故障，主要原因是网线老化。为了提升系统稳定性，我们决定更换所有网线，你来处理一下吧。” 你略感疑惑：“只是更换网线吗？” 面试官点了点头：“没错，但需要满足一些特殊要求： 1. 我们准备了三种颜色的网线：红色、绿色和蓝色。你需要为每两台服务器之间选择其中一种颜色的网线进行连接。 2. 为了避免单点故障，不能只使用一种颜色的网线就覆盖所有服务器之间的通信。也就是说，仅通过一种颜色的网线，**无法从任意一台服务器访问到其他所有服务器**。 3. 为了保证网络性能，每台服务器都至少要通过一条红色网线与其他服务器连接。 4. 红色网线要尽可能多的被使用。” 你站起身准备走人。 “等等！”面试官拉住了你，“这样吧，如果你能算出满足以上条件的方案总数，我就给你开 Super Special Offer！” “行！” 现在，请你计算出满足以上条件的方案数。由于答案可能很大，你只需要输出方案数对 $10^9 + 7$ 取模的结果即可。 > 如果两种网线连接方案中存在任意两台服务器之间的网线颜色不同，则被认为是两种不同的方案。 ### 输入格式 输入的第一行包含一个整数 $t$（$1\leq t \leq 10^5$），表示有 $t$ 组测试数据。 接下来的 $t$ 行中，每行包含一个整数 $N$ $(4 \leq N \leq 10^9)$，表示服务器的数量。 ### 输出格式 对于每组测试数据，输出一个整数，表示满足条件的方案总数对 $10^9+7$ 取模后的结果。 ### 样例输入 ```text 1 4 ``` ### 样例输出 ```text 18 ``` ### 样例说明