FAST2 - Fast Sum of two to an exponent

no tags 

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

hide comments
charlles: 2019-04-10 17:52:22

bitwise operations turn it easy. ;)

imkiller: 2018-06-01 15:15:14

Use pefixSum and precompute it so that u can retrive in O(1)
PythonRocks!

dragon_fury: 2015-11-03 16:10:58

python rocks...... :D

Thotsaphon Thanatipanonda: 2015-10-21 09:30:43

Finally, Java can pass this problem!! :D

dwij28: 2015-10-01 16:29:10

Used sys library in python for input, input() function results in TLE, also modular exponentiation gives TLE .. A hint here : think of the fastest way to find 2 ** n, there is a very fast method to do this, and you do not require any exponent functions for this .. :)

gullu_mishra: 2015-09-18 18:28:04

Lovely python ... u rock baby ;-)

Parul Yadav: 2015-09-07 13:23:36

my first q in python

Vladimir: 2015-08-05 17:42:06

Edit: nevermind

Last edit: 2015-08-05 17:45:17
(Tjandra Satria Gunawan)(曾毅昆): 2012-05-04 02:53:09

No need to use BigInt ;)
Only use int64 string 3:D


Added by:Rocker3011
Date:2012-04-14
Time limit:0.100s
Source limit:500B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem