TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P8257
  • Problem
  • P8257灭鼠行动
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 3s 256MB
    Description

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

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

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

    Input Format

    输入包含多组数据。

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

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

    Output Format

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

    Sample Input

    2
    1
    527

    Sample Output

    2
    482383063