Read problems statements in  Mandarin Chinese  and  Russian. 
A new school in Byteland is now in the process of renewing some classrooms with new, stronger and better chairs, so that the students can stay still and pay attention to class :)

However, due to budget and logistic reasons, it's only possible to carry a chair at a time to the classroom, which means that for a long time, many students will be up, waiting for their chair to arrive.

The teacher, however, as she is very clever, decided to challenge her students with a problem: "Imagine that there are N students in the classroom and that there are only K chairs. In how many ways, can I choose K elements from the class to sit down, if I see them as being distinct?" 

Lira replied immediately with the right answer, so, the teacher decided to make the game a little funnier: "Okay Lira, as you are so fast, now I want you to tell me exactly the same thing, but, with the addition that the value of K is changing, this is, I want you to tell me the sum of the number of ways I can sit down K of you, if the value of K goes from 1 (meaning that there are no chairs in the classroom but one) to N (meaning that all of your chairs arrived). Can you be as fast now? As the answer might get large I want you to tell me the result modulo 1000000007. (10^{9} + 7)"

As you might have noticed, it's time for you to help Lira solving this variant of the problem. :D 

------ Input ------ 

The first line of the input file contains an integer T, denoting the number of test cases on the input file.

Afterwards, T lines follow, each containing an integer N, the number of students that the teacher will try to sit down as the number of chairs goes from 1 to N.

------ Output ------ 

For each test case, you should output an integer, denoting the sum of the number of ways the teacher can make N students sit down on K chairs, as K goes from 1 to N, modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100000000$
 
----- Sample Input 1 ------ 
2
1
2
----- Sample Output 1 ------ 
1
3

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
def modPower(a, b, m):
	if b == 0:
		return 1
	elif b == 1:
		return a % m
	t = modPower(a, b // 2, m)
	if b % 2 == 0:
		return t % m * t % m % m
	else:
		return t % m * t % m * a % m % m
for _ in range(int(input())):
	n = int(input())
	print(modPower(2, n, 1000000007) - 1)


t = int(input())
for val in range(0, t):
	n = int(input())
	print(pow(2, n, 1000000007) - 1)


b = pow(10, 9) + 7
for _ in range(int(input())):
	a = int(input())
	print(pow(2, a, b) - 1)


s = 1000000007

def power(n):
	(ans, x) = (1, 2)
	while n != 0:
		if n & 1 == 1:
			ans = ans * x % s
		x = x * x % s
		n = n >> 1
	return ans % s
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		value = (power(n) - 1 + s) % s
		print(value)


tests = int(input())
for i in range(tests):
	n = int(input())
	print(pow(2, n, 10 ** 9 + 7) - 1)


tcase = int(input())
mod = 1000000007
while tcase > 0:
	tcase -= 1
	n = int(input())
	print(pow(2, n, mod) - 1)


for i in range(int(input())):
	n = int(input())
	print(pow(2, n, 1000000007) - 1)


for _ in range(int(input())):
	n = int(input())
	mod = 10 ** 9 + 7
	var = (pow(2, n, mod) - 1) % mod
	print(var)


from math import factorial
try:
	for i in range(int(input())):
		n = int(input())
		print(pow(2, n, 1000000007) - 1)
except:
	pass


tests = int(input())
for i in range(tests):
	num = int(input())
	ans = pow(2, num, 10 ** 9 + 7)
	print(ans - 1)


mod = 1000000007

def power(n):
	if n == 0:
		return 1
	u = power(int(n / 2))
	u = u * u % mod
	if n & 1:
		u = u << 1
	return u % mod
for _ in range(int(input())):
	n = int(input())
	print(power(n) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	mod = 1000000007
	print((pow(2, n, mod) - 1) % mod)


import math
n = int(input())
for x in range(n):
	a = int(input())
	a = 1 << a
	print((a - 1) % 1000000007)


t = int(input())
for j in range(t):
	m = 1000000007
	n = int(input())
	print(pow(2, n, m) - 1 % m)


def power(a, b):
	if b == 0:
		return 1
	x = power(a, b // 2)
	if b % 2 == 0:
		return x % 1000000007 * x % 1000000007 % 1000000007
	else:
		return x % 1000000007 * (x * a) % 1000000007 % 1000000007
for _ in range(int(input())):
	n = int(input())
	n = n % 1000000007
	m = power(2, n)
	m = m % 1000000007
	print(m - 1)


n = 10
for k in range(int(input())):
	p = int(input())
	k = pow(2, p, 10 ** 9 + 7) - 1
	print(k)


e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	x = pow(2, n, e)
	print((x - 1) % e)


t = int(input())
while t:
	n = int(input())
	ans = pow(2, n, 1000000007) - 1
	print(ans)
	t -= 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	m = 10 ** 9 + 7
	k = pow(2, n, m)
	print((k - 1) % m)


MOD = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	ans = pow(2, n, MOD) - 1
	print(ans)


def power_2(n):
	if n == 0:
		return 1
	x = power_2(n // 2)
	if n % 2 == 0:
		return x % 1000000007 * (x % 1000000007) % 1000000007
	else:
		return x % 1000000007 * (x % 1000000007) * 2 % 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	print(power_2(n) - 1)


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		print((pow(2, n, mod) - 1) % mod)


import math
m = 10 ** 9 + 7
powers = []
for i in range(27):
	powers.append(0)
powers[-1] = 2
i = 25
while i >= 0:
	powers[i] = powers[i + 1] ** 2 % m
	i -= 1

def get_bin(n, l):
	ans = []
	for i in range(l):
		ans.append(n % 2)
		n //= 2
	ans.reverse()
	return ans
for t in range(int(input())):
	n = int(input())
	bi = get_bin(n, 27)
	ans = 1
	for i in range(len(bi)):
		if bi[i] == 1:
			ans = ans * (powers[i] % m) % m
	print(ans - 1)


for tc in range(int(input())):
	n = int(input())
	a = pow(2, n, 1000000007) - 1
	print(a)


for _ in range(int(input())):
	w = 1000000007
	n = int(input())
	ans = pow(2, n, w)
	print(ans - 1)


for i in range(int(input())):
	a = int(input())
	print(pow(2, a, 1000000007) - 1)


t = input()
mod = 10 ** 9 + 7
for c in range(0, int(t)):
	n = int(input())
	ans = pow(2, n, mod) - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	c = pow(2, n, 1000000007) - 1
	print(c)


for _ in range(int(input())):
	print(pow(2, int(input()), 1000000007) - 1)


T = int(input())
for i in range(T):
	N = int(input())
	s = pow(2, N, 10 ** 9 + 7) - 1
	print(s)


t = int(input())
for i in range(0, t):
	n = int(input())
	c = pow(2, n, 1000000007) - 1
	print(c)


for tc in range(int(input())):
	n = int(input())
	print(pow(2, n, 10 ** 9 + 7) - 1)


MOD = 1000000007

def fast_exp(a, b):
	if b == 0:
		return 1
	x = fast_exp(a, b // 2)
	x = x * x % MOD
	if b & 1:
		x = x * a % MOD
	return x
t = int(input())
while t:
	t -= 1
	n = int(input())
	print(fast_exp(2, n) - 1)


def power_2(N):
	if N == 0:
		return 1
	x = power_2(N // 2)
	if N % 2 == 0:
		return x % 1000000007 * (x % 1000000007) % 1000000007
	else:
		return x % 1000000007 * (x % 1000000007) * 2 % 1000000007
T = int(input())
for t in range(T):
	N = int(input())
	print((power_2(N) - 1) % 1000000007)


T = int(input())
M = 10 ** 9 + 7
for i in range(T):
	N = int(input())
	ans = pow(2, N, M) - 1
	print(int(ans))


t = int(input())
while t > 0:
	n = int(input())
	x = pow(2, n, 1000000007)
	print(x - 1)
	t -= 1


for u in range(int(input())):
	n = int(input())
	print(pow(2, n, 1000000007) - 1)