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

Input

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

Each line contains the number "n".

0 ≤ n ≤ 500

Output

Output the sum from 2⁰ to 2ⁿ MODULO 1298074214633706835075030044377087.

Example

Input:
3
0
1
2

Output:
1
3
7

Extra: TLE is equal to 0.15s