There is people that really like to do silly thinks, one of them is sum the numbers from 2^0 to 2^n, task is actually really simple, just do a ultra fast sum of term 2^0 to 2^n

Input

the first line starts with a number, T, wich is the number of test cases, T lines will follow

each line contains a number "n" that is the nth term of the sum from 2^0 to 2^n

0<=n<=500

Output

Output the sum from 2^0 to 2^n MODULO 1298074214633706835075030044377087

Example

Input:
3
0
1
2

Output:
1
3
7 

Extra: TLE is equal to 0.15s