Start: 2023-05-29 00:00:00

机房最菜oier的比赛

End: 2023-06-01 00:00:00
Now　 2025-12-16 17:20:12　 类型: IOI　 状态: Ended　

P2. 巨佬的计算
Description

众所周知,wky巨佬是很擅长计算的,他能在 0.0000000000001

秒内计算2的幂次

有T次询问,每次一个数n,求(1<<n)对1e9+7取模的值

Input

第1行一个数T\

接下来T行 每行一个数n,求(1<<n)对1e9+7取模的值


Output

共T行 每行一个数x 表示(1<<n)对1e9+7取模的值

Examples

Input

3
1
4
9

Output

2
16
512

Input

4
0
3
2
5

Output

1
8
4
32
Hint

对于20%的数据 T<=10,0<=N<=50

对于60%的数据 T<=10^5,0<=N<=5*10^5

对于100%的数据 T<=10^7,0<=N<=2*10^7


Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit