一个村子里有许多间房子,按照顺序,它们被编号为$123\cdots2^n$.
如此多的房子也引来了许多老鼠,但老鼠们似乎对某些编号的房子情有独钟.具体来说,编号为$x$的房子里有老鼠,当且仅当$3x \oplus x=2x$,其中$\oplus$表示异或运算.
村委会决定开展灭鼠行动,当前的首要任务就是统计村子里有老鼠的房子的数量.由于这个数字非常大,你只需要输出其对$10^9+7$取模的结果即可.
输出共$T$行,每行包含一个整数,其中第$i$行的整数表示,对于第$i$组数据,有老鼠的房子的数量,对$10^9+7$取模的结果.