题目描述
青青是一个刚开始学习OI的可爱的小孩。最近,老师给他们讲了位运算的一些知识,并且布置给了他们一道作业:给定一个n,请问在0<=x<=2^n-1的范围内,有多少个数满足x xor 2x xor 3x = 0 这个式子?青青不太会做,所以只好向你求助了。
输入格式
输入包含多组数据,第一行是一个数T(1<=T<=200000),表示数据的组数。
接下来有T行,每行是一个数n(1<=n<=500000),表示题目要求给的数。
由于答案有可能很大,请将答案对1000000009取余数。
输出格式
输出有T行,每行有一个数,表示题目所要求的答案。
样例输入
样例输出