TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8257
  • 题目
  • P8257灭鼠行动
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 3s 256MB
    问题描述

    一个村子里有许多间房子,按照顺序,它们被编号为$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$取模的结果。

    样例输入

    2
    1
    527

    样例输出

    2
    482383063