PID643 / 青青的异或式子
题目描述

青青是一个刚开始学习OI的可爱的小孩。最近,老师给他们讲了位运算的一些知识,并且布置给了他们一道作业:给定一个n,请问在0<=x<=2^n-1的范围内,有多少个数满足x xor 2x xor 3x = 0 这个式子?青青不太会做,所以只好向你求助了。

输入格式

输入包含多组数据,第一行是一个数T(1<=T<=200000),表示数据的组数。

接下来有T行,每行是一个数n(1<=n<=500000),表示题目要求给的数。

由于答案有可能很大,请将答案对1000000009取余数。

输出格式

输出有T行,每行有一个数,表示题目所要求的答案。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论