Algorithm

Problem link- https://www.spoj.com/problems/FAST2/

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

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

f = [0] * 505
f[0] = 2
for i in range(1, 505):
    f[i] = f[i - 1] * 2 % 1298074214633706835075030044377087
T = int(input())
for i in range(T):
    N = int(input())
    print(f[N] - 1)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
0
1
2

Output

x
–
+
cmd
1
3
7
Advertisements

Demonstration

SPOJ Solution-Fast Sum of two to an exponent-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python