一个村子里有许多间房子，按照顺序，它们被编号为$1,2,3,\cdots,2^n$。

如此多的房子也引来了许多老鼠，但老鼠们似乎对某些编号的房子情有独钟。具体来说，编号为$x$的房子里有老鼠，当且仅当$3x \oplus x=2x$，其中$\oplus$表示异或运算。

村委会决定开展灭鼠行动，当前的首要任务就是统计村子里有老鼠的房子的数量。由于这个数字非常大，你只需要输出其对$10^9+7$取模的结果即可。

输入包含多组数据。

第一行，输入一个整数$1 \leqslant T \leqslant 10^6$，表示数据组数。

接下来$T$行，第$i$行一个整数 $1 \leqslant n_i \leqslant 10^{6}$，表示在第 \(i\) 组数据中，房子的数量为 $2$ 的 \(n_i\) 次方。

输出共$T$行，每行包含一个整数，其中第$i$行的整数表示，对于第$i$组数据，有老鼠的房子的数量，对$10^9+7$取模的结果。