Migrated from Lutece 2498 yasra dius manaf

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

——みとせのりこ - EXEC_SUSPEND/.

有一个 $n\times n$ 的正方形格子图，每个格子大小为 $1\times 1$。现在一共有 $3$ 种颜色，要给每一个格子都染上其中一种颜色。问有多少种染色方案，使得存在至少一行或者一列的颜色相同？答案对 $10^9+7$ 取模。

Input

第一行一个正整数 $T$，代表有 $T$ 组数据；

接下来对于每一组数据输入一个正整数 $n$.

Output

对于每一组数据，输出一行一个整数表示答案对 $10^9+7$ 取模后的结果。

Samples

2
1
2

3
63

Constraints

$1\le T\le 30, 1\le n \le 10^6$

对于单个测试点，$n\ge 10^5$ 不超过 $10$ 组.

Resources

2020 UESTC ICPC Training for Math and Geometry