Given N, count how many permutations of [1, 2, 3, ..., N] satisfy the following property.

Let P1, P2, ..., PN denote the permutation. The property we want to satisfy is that there exists an i between 2 and n-1 (inclusive) such that

- Pj > Pj + 1  ∀    i ≤ j ≤ N - 1.
- Pj > Pj - 1  ∀    2 ≤ j ≤ i.

-----Input-----
First line contains T, the number of test cases. Each test case consists of N in one line.

-----Output-----
For each test case, output the answer modulo 109+7.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 109

-----Subtasks-----
- Subtask #1(40 points): 1 ≤ N ≤ 1000
- Subtask #2(60 points): original constraints

-----Example-----
Input:
2
2
3

Output:
0
2

-----Explanation-----

Test case 1:

No permutation satisfies.

Test case 2:

Permutations [1, 3, 2] and [2, 3, 1] satisfy the property.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
MOD = int(1000000000.0 + 7)
for _ in range(int(input())):
	n = input()
	n = int(n)
	if n <= 2:
		print('0')
		continue
	print(pow(2, n - 1, MOD) - 2)


t = int(input(''))
for i in range(t):
	n = int(input(''))
	if n == 1:
		print('0')
	else:
		ans = pow(2, n - 1, 1000000007)
		print((ans - 2) % 1000000007)


try:
	for _ in range(int(input())):
		n = int(input())
		print(0) if n == 1 else print(pow(2, n - 1, 10 ** 9 + 7) - 2)
except EOFError:
	pass


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input()) - 1
	if N <= 1:
		print(0)
		continue
	val = 1
	dva = 2
	while N:
		if N & 1:
			val *= dva
			val %= MOD
		dva *= dva
		dva %= MOD
		N >>= 1
	val -= 2
	if val < 0:
		val += MOD
	print(val)


MOD = 1000000007

def modex(a, p, m):
	if int(p) is 0:
		return 1
	if int(p) & 1:
		k = modex(a, p / 2, m)
		return k * k % m * a % m
	k = modex(a, p / 2, m)
	return k * k % m

def main():
	t = int(input())
	while t is not 0:
		t -= 1
		n = int(input())
		if n is 1:
			print(0)
		else:
			print((modex(2, n - 1, MOD) - 2 + MOD) % MOD)
main()


modulo = 1000000007

def pow(a, n):
	res = 1
	while n > 0:
		if n & 1:
			res *= a
			res %= modulo
		a *= a
		a %= modulo
		n //= 2
	return res
T = int(input())
for t in range(T):
	n = int(input())
	if n > 2:
		print((pow(2, n - 1) - 2) % modulo)
	else:
		print(0)


import sys, math
MOD = 10 ** 9 + 7
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	print((pow(2, n - 1, MOD) - 2) % MOD if n > 2 else 0)


MOD = 10 ** 9 + 7

def powerMod(b, e, m):
	x = 1
	while e > 0:
		if e % 2 == 1:
			x = x * b % m
			e = e - 1
		else:
			b = b * b % m
			e = e // 2
	return x
t = int(input())
while t > 0:
	n = int(input())
	if n < 3:
		print(0)
	else:
		ans = powerMod(2, n - 1, MOD) - 2
		if ans < 1:
			ans = ans + MOD
		print(ans)
	t = t - 1


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


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


bf = int(input())
for bf in range(bf):
	h = int(input())
	if h > 1:
		h = h - 1
	d = pow(2, h, 1000000007)
	print(d - 2)


def calcMod(b):
	a1 = 2
	p = 1
	while b > 0:
		if b % 2 != 0:
			p = p * a1
			p = p % 1000000007
		b = b // 2
		a1 = a1 * a1 % 1000000007
	return p
t = int(input())
for i in range(t):
	n = int(input())
	if n < 3:
		print(0)
	else:
		print(calcMod(n - 1) - 2)


i = int(input())
MOD = int(1000000000.0 + 7)
while i:
	n = int(input())
	if n <= 2:
		print(0)
	else:
		print(pow(2, n - 1, MOD) - 2)
	i -= 1


def twop(n):
	if n == 0:
		return 1
	if n == 1:
		return 2
	k = n // 2
	if n % 2 == 0:
		return (twop(k) % 1000000007) ** 2 % 1000000007
	else:
		return (twop(k) % 1000000007) ** 2 * 2 % 1000000007
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('0')
		continue
	print(twop(n - 1) - 2)


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


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


mod = 1000000007
T = int(input())
for _ in range(T):
	N = int(input())
	if N < 3:
		print(0)
	else:
		print((pow(2, N - 1, mod) + mod - 2) % mod)


def mod_exp(num, pow, mod):
	answer = 1
	while pow > 0:
		if pow & 1 == 1:
			answer = answer * num % mod
		num = num * num % mod
		pow = pow >> 1
	return answer
modulo = 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	answer = mod_exp(2, n - 1, modulo)
	answer = answer - 2
	if answer < 0:
		answer = answer + n
	print(answer)


mod = int(10 ** 9 + 7)
t = int(input())
while t:
	n = int(input())
	if n > 2:
		total_combination = pow(2, n - 1, mod) - 2
	else:
		total_combination = 0
	print(int(total_combination))
	t -= 1


def modexp_rl(a, b, n):
	r = 1
	while b > 0:
		if b % 2 == 1:
			r = r * a % n
		a = a * a % n
		b = b // 2
	return r % n
t = int(input())
for i in range(0, t):
	n = int(input())
	if n > 2:
		n = (modexp_rl(2, n - 1, 1000000007) - 2) % 1000000007
	elif n <= 2:
		n = 0
	print(n)


t = int(input())
M = 10 ** 9 + 7
while t:
	x = 2
	result = 1
	t -= 1
	n = int(input())
	if n <= 2:
		print(0)
	else:
		y = n - 1
		while y:
			if y % 2 == 1:
				result = result * x % M
			y = y // 2
			x = x * x % M
		print(result - 2)


def modularExponentiation(x, n, M):
	result = 1
	while n > 0:
		if n % 2 == 1:
			result = result * x % M
		x = x * x % M
		n = n // 2
	return result
for _ in range(int(input())):
	n = int(input())
	print('0') if n <= 2 else print((modularExponentiation(2, n - 1, 1000000007) - 2) % 1000000007)


mod = 10 ** 9 + 7

def pow(a, b):
	x = 1
	while b:
		if b % 2 == 1:
			x *= a
			x %= mod
		b //= 2
		a *= a
		a %= mod
	return x
for t in range(int(input())):
	n = int(input())
	if n <= 2:
		print(0)
	else:
		y = pow(2, n - 1) - 2
		print(y)


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


m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0)
	else:
		g = pow(2, n - 1, m) - 2
		print(g)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	a = int(input())
	if a == 0 or a == 1 or a == 2:
		print(0)
	else:
		print((pow(2, a - 1, MOD) - 2) % MOD)


t = int(input())
for _ in range(t):
	n = int(input())
	if n <= 2:
		print(0)
		continue
	ans = 1
	sq = 2
	n -= 1
	while n > 0:
		if n % 2 == 1:
			ans = ans * sq % 1000000007
		sq = sq * sq % 1000000007
		n //= 2
	ans -= 2
	ans %= 1000000007
	if ans < 0:
		ans += 1000000007
	print(ans)


def main():
	from sys import stdin, stdout
	MOD = int(1000000000.0) + 7

	def power(a, b):
		if b == 0:
			return 1
		if b & 1:
			return a * power(a, b - 1) % MOD
		else:
			return power(a * a % MOD, b >> 1) % MOD
	for _ in range(int(stdin.readline())):
		n = int(stdin.readline())
		n -= 2
		if n > 0:
			n = ((power(2, n) - 1) % MOD << 1) % MOD
		else:
			n = 0
		stdout.write(str(n) + '\n')
main()


import math
for _ in range(int(input())):
	n = int(input())
	if n > 1:
		n = n - 1
	a = pow(2, n, 1000000007)
	a = a - 2
	print(a)


T = int(input(''))
for i in range(T):
	N = int(input(''))
	if N == 1:
		print('0')
	else:
		ans = pow(2, N - 1, 1000000007)
		print((ans - 2) % 1000000007)


t = int(input())
m = pow(10, 9) + 7

def calcPower(x, y):
	v = 1
	while y > 0:
		if y % 2 == 1:
			v = v * x % m
		x = x * x % m
		y = y // 2
	return v
while t != 0:
	n = int(input())
	if n in [1, 2]:
		print(0)
	else:
		f = calcPower(2, n - 2)
		print((2 * f - 2) % m)
	t -= 1


def pow_mod(x, y, z):
	nn = 1
	while y:
		if y & 1:
			nn = nn * x % z
		y >>= 1
		x = x * x % z
	return nn
mod = 1000000007
t = int(input().strip())
while t > 0:
	n = int(input().strip())
	if n is 1 or n is 2:
		print(0)
	else:
		n -= 1
		ans = pow_mod(2, n, mod)
		print(ans - 2)
	t -= 1


import sys, math, string, fractions, functools, collections
sys.setrecursionlimit(10 ** 7)
RI = lambda x=' ': list(map(int, input().rstrip().split(x)))
RS = lambda x=' ': input().rstrip().split(x)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
mod = int(1000000000.0 + 7)
eps = 1e-06
MAX = 1010
T = RI()[0]
for i in range(T):
	N = RI()[0]
	if N == 1 or N == 2:
		print(0)
	else:
		print((pow(2, N - 1, mod) + (mod - 2)) % mod)


import math
r = 1000000007

def func1(i):
	if i < 50:
		return (1 << i) % r
	f = func1(i // 2) % r
	if i % 2:
		return 2 * f * f % r
	else:
		return f * f % r
t = int(input())
ans = []
for _ in range(t):
	i = int(input())
	if i in (1, 2):
		ans.append(0)
	else:
		ans.append(func1(i - 1) - 2)
for a in ans:
	print(a)


from math import factorial
mod = 10 ** 9 + 7

def exponentiation(bas, exp, mod=10 ** 9 + 7):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def soln(n: int) -> int:
	if n <= 2:
		return 0
	return (pow(2, n - 1, mod) - 2) % mod
for _ in range(int(input())):
	n = int(input())
	print(soln(n))


cases = int(input())
for _ in range(cases):
	N = int(input())
	print(max(0, pow(2, N - 1, 10 ** 9 + 7) - 2))


MOD = 1000000007

def power(x, n):
	if n == 0:
		return 1
	if n % 2 == 0:
		return power(x * x % MOD, n / 2)
	else:
		return x * power(x * x % MOD, int(n / 2)) % MOD
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		ans = 0
	else:
		ans = (power(2, n - 1) - 2) % MOD
	print(ans)


from sys import stdin
t = int(stdin.readline())
while t:
	n = int(stdin.readline())
	if n == 1:
		print(0)
	else:
		print((pow(2, n - 1, 1000000007) - 2) % 1000000007)
	t -= 1


def modular_pow(base, exponent, modulus):
	if modulus == 1:
		return 0
	result = 1
	base = base % modulus
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		exponent = exponent >> 1
		base = base * base % modulus
	return result
for tests in range(int(input())):
	N = int(input())
	if N < 3:
		print(0)
	else:
		a = modular_pow(2, N - 1, 10 ** 9 + 7) - 2
		if a < 0:
			print(a + 10 ** 9 + 7)
		else:
			print(a)


t = int(input().strip())
for i in range(0, t):
	n = int(input().strip())
	if n < 3:
		print(0)
	else:
		print(pow(2, n - 1, 1000000007) - 2)


M = 1000000007
tests = int(input())
results = []
for i in range(0, tests):
	n = int(input())
	if n <= 2:
		results.append(0)
	else:
		val = pow(2, n - 1, M)
		results.append(val - 2)
for xx in results:
	print(xx)


mod = 10 ** 9 + 7

def main():
	if n == 1 or n == 2:
		print(0)
		return
	print((pow(2, n - 1, mod) - 2) % mod)
t = int(input())
for _ in range(t):
	n = int(input())
	main()


import sys
sys.setrecursionlimit(50000000)

def read(var_type=int):
	n = var_type(input())
	return n

def read_array(var_type=int):
	arr = tuple((var_type(n) for n in input().split()))
	return arr
PRIME = 10 ** 9 + 7

def mod_pow(b, e):
	if e == 0:
		return 1
	p = mod_pow(b, e // 2)
	p = p * p % PRIME
	if e % 2 == 1:
		p = p * b % PRIME
	return p
t = read()
for i in range(t):
	n = read()
	if n <= 2:
		print(0)
	else:
		ans = mod_pow(2, n - 1)
		ans = (ans + PRIME - 2) % PRIME
		print(ans)


for i in range(int(input())):
	n = int(input())
	if n > 2:
		print((pow(2, n - 1, 1000000007) + 1000000005) % 1000000007)
	else:
		print(0)


m = int(1000000000.0) + 7
T = int(input())
for t in range(T):
	N = int(input())
	if N == 1:
		N = 2
	print((pow(2, N - 1, m) - 2 + m) % m)


import sys
MOD = 10 ** 9 + 7
t = int(sys.stdin.readline())
for _t in range(t):
	n = int(sys.stdin.readline())
	sys.stdout.write('{}\n'.format(0 if n < 3 else pow(2, n - 1, MOD) - 2))


test = int(input(''))
while test:
	n = int(input(''))
	if n == 1 or n == 2:
		print(0)
	else:
		n = n - 1
		kok = pow(2, n, 1000000007)
		kok = kok - 2
		print(kok)
	test = test - 1


import math
t = int(input())
while t:
	n = int(input())
	if n == 1 or n == 2:
		print(0)
	else:
		print((pow(2, n - 1, 10 ** 9 + 7) - 2) % (10 ** 9 + 7))
	t -= 1


def pow(a, b):
	if b == 0:
		m = 1
	elif b == 1:
		m = 2
	else:
		m = pow(a, b // 2)
		m = m * m % (1000000000 + 7)
		if b % 2 == 1:
			m = m * a % (1000000000 + 7)
	return m
for i in range(int(input())):
	c = int(input())
	p = pow(2, c - 1)
	p = (p - 2) % (1000000000 + 7)
	if c == 1:
		print(0)
	else:
		print(p)


for t in range(int(input())):
	print((pow(2, max(int(input()) - 1, 1), 1000000007) - 2 + 1000000007) % 1000000007)


def main():
	mod = 10 ** 9 + 7
	for _ in range(int(input())):
		n = int(input())
		res = pow(2, n - 1, mod)
		res = res - 2
		if res < 0:
			res = 0
		print(res)
main()


t = int(input())
mod = 1000000007
while t:
	n = int(input())
	if n == 1:
		print(0)
	else:
		f = n - 1
		ans = pow(2, f, mod) - 2
		print(ans)
	t = t - 1


t = int(input())

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
out = []
c = 1000000007
for i in range(0, t):
	n = int(input())
	if n == 1 or n == 2:
		out.append(0)
	else:
		out.append(pow_mod(2, n - 1, c) - 2)
for i in out:
	print(i)


t = int(input())
for i in range(t):
	x = int(input())
	if x <= 2:
		print(0)
	else:
		print(pow(2, x - 1, 1000000007) - 2)


mod = 1000000007

def pow(base, exp):
	X = base
	E = exp
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % mod
			E = E / 2
		else:
			Y = X * Y % mod
			E = E - 1
	return Y
t = int(input())
for i in range(0, t):
	n = int(input())
	if n == 1:
		print(0)
	else:
		print(pow(2, n - 1) - 2)


mod = 10 ** 9 + 7

def modexp(base, exp):
	res = 1
	base = base % mod
	while exp > 0:
		if exp % 2 == 1:
			res = res * base % mod
		exp >>= 1
		base = base * base % mod
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	if n < 3:
		print(0)
	else:
		ans = (modexp(2, n - 1) - 2 + mod) % mod
		print(ans)


mod = 7 + 10 ** 9

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
T = int(input())
for _ in range(T):
	n = int(input())
	if n < 3:
		ans = 0
	elif n == 3:
		ans = 2
	else:
		ans = 2 * (pow_mod(2, n - 2, mod) - 1)
		ans %= mod
	print(ans)


def poww(a, b, m):
	if b == 0:
		return 1 % m
	elif b == 1:
		return a % m
	elif b % 2 == 0:
		temp = poww(a, b // 2, m)
		return temp * temp % m
	else:
		temp = poww(a, b // 2, m)
		return temp * temp * a % m
t = int(input())
modd = 10 ** 9 + 7
while t:
	n = int(input())
	if n == 1:
		print(0)
	else:
		print((poww(2, n - 1, modd) % modd - 2) % modd)
	t -= 1


R = 1000000007

def power12(a, b):
	if b == 0:
		return 1
	temp = power12(a, b // 2) % R
	if b % 2 == 0:
		return temp * temp % R
	if b % 2 == 1:
		return temp * temp % R * a % R
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n <= 2:
		ans = 0
	else:
		ans = (power12(2, n - 1) - 2) % R
	print(ans)