Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You have become good friends with Chef. Right now, Chef is busy in the kitchen, so he asked you to solve a problem for him.

Consider a list of integers $L$. Initially, $L$ contains the integers $1$ through $N$, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in $L$ is not important. You should perform the following operation $N-1$ times:
Choose two elements of the list, let's denote them by $X$ and $Y$. These two elements may be equal.
Erase the chosen elements from $L$.
Append the number $X + Y + X \cdot Y$ to $L$.

At the end, $L$ contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo $1,000,000,007$ ($10^{9}+7$).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $N$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum possible value of the final number in the list modulo $10^{9}+7$.

------  Constraints ------
$1 ≤ T ≤ 100,000$
$1 ≤ N ≤ 1,000,000$

------  Subtasks ------
Subtask #1 (20 points): $1 ≤ T, N ≤ 25$ 

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
3

1

2

4
----- Sample Output 1 ------ 
1

5

119
----- explanation 1 ------ 
Example case 1: $L=[1]$

Example case 2: $L=[1,2] \rightarrow [1 + 2 + 1 \cdot 2] $

Example case 3: $L=[\textbf{1},2,3,\textbf{4}] \rightarrow [\textbf{2},3,\textbf{9}] \rightarrow [3,29] \rightarrow [119] $. The chosen elements in each step are in bold.

Difficulty: MEDIUM
Tags: Preprocessing

Starter code:

Solutions:
t = int(input())
ar = []
for _ in range(t):
	n = int(input())
	ar.append(n)
mx = max(ar)
dic = {1: 1}
for i in range(2, mx + 1):
	vl = i
	lst = dic[vl - 1]
	nxt = lst + vl + lst * vl
	dic[vl] = nxt % (10 ** 9 + 7)
for i in ar:
	print(dic[i])


a = list(range(1, 1000001))
for i in range(1, 1000000):
	a[i] = (a[i] + a[i - 1] + a[i] * a[i - 1]) % 1000000007
for _ in range(int(input())):
	print(a[int(input()) - 1])


MOD = 10 ** 9 + 7
dp = [0]
for i in range(1, 10 ** 6 + 1):
	dp.append((dp[-1] * i + dp[-1] + i) % MOD)
t = int(input())
for _ in range(t):
	print(dp[int(input())])


L = [0 for _ in range(0, 1000000)]
L[0] = 1
m = 1000000007
for i in range(1, 1000000):
	L[i] = (L[i - 1] + i + 1 + (i + 1) * L[i - 1]) % m
for _ in range(int(input())):
	N = int(input())
	print(L[N - 1])


l = [0] * 1000001
s = 10 ** 9 + 7
for i in range(1, 10 ** 6 + 1):
	l[i] = (i + l[i - 1] + i * l[i - 1]) % s
for _ in range(int(input())):
	n = int(input())
	print(l[n])


s = 1000000007
l = [0] * 10000001
for i in range(1, 10 ** 6 + 1):
	l[i] = (l[i - 1] + i + i * l[i - 1]) % s
for _ in range(int(input())):
	n = int(input())
	print(l[n])


factorial_array = []
prime = 10 ** 9 + 7
initial = 1
for i in range(2, 1000003):
	factorial_array.append(initial)
	initial *= i
	initial %= prime
for _ in range(int(input())):
	n = int(input())
	print((factorial_array[n] + prime - 1) % prime)


l = [1] * 1000000
k = len(l)
for i in range(1, k):
	l[i] = (l[i - 1] + i + 1 + l[i - 1] * (i + 1)) % 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(1)
		continue
	print(l[n - 1])


l = [0, 1]
x = 1
for y in range(2, 1000002):
	k = (x + y + x * y) % 1000000007
	l.append(k)
	x = k
for _ in range(int(input())):
	n = int(input())
	print(l[n])


l = [0, 1]
ans = 1
mod = 10 ** 9 + 7
for i in range(2, 1000001):
	ans = (ans + i + i * ans) % mod
	l.append(ans)
for _ in range(int(input())):
	n = int(input())
	print(l[n])


full = list(range(1, 1000002))
c = 1000000007
for i in range(1, 1000001):
	full[i] = (full[i - 1] + full[i] + full[i] * full[i - 1]) % c
for _ in range(int(input())):
	n = int(input())
	print(full[n - 1])


mod = 1000000007
a = []
for i in range(1000001):
	a.append(i + 1)
for i in range(1, 1000001):
	a[i] = (a[i - 1] + a[i] + a[i - 1] * a[i]) % mod
t = int(input())
for _ in range(t):
	n = int(input())
	print(a[n - 1])


t = int(input())
l = [0] * 1000001
l[0] = 1
for i in range(1, 1000001):
	l[i] = l[i - 1] * (i + 1) % 1000000007
for i in range(t):
	n = int(input())
	print(l[n] - 1)


res = [0, 1]
X = 1
for Y in range(2, 1000001):
	i = (X + Y + X * Y) % 1000000007
	res.append(i)
	X = i
T = int(input())
for _ in range(T):
	N = int(input())
	print(res[N])


lst = [1]
for z in range(int(input())):
	n = int(input())
	mod = pow(10, 9) + 7
	while len(lst) < n + 2:
		lst.append(lst[-1] * len(lst) % mod)
	print(lst[n + 1] - 1)


T = int(input())
l = [0] * 1000001
l[0] = 1
for i in range(1, 1000001):
	l[i] = l[i - 1] * (i + 1) % 1000000007
for x in range(T):
	n = int(input())
	print(l[n] - 1)


from sys import stdin
stdint = lambda : int(stdin.readline())
mod = int(1000000000.0) + 7
maxRange = 1000001
dp = [0] * maxRange
dp[1] = 1
for i in range(2, maxRange):
	dp[i] = (dp[i - 1] + i + dp[i - 1] * i) % mod
for _ in range(stdint()):
	n = stdint()
	print(dp[n])


t = int(input())
dp = [0] * 1000002
dp[1] = 1
for i in range(2, 1000002):
	dp[i] = dp[i - 1] * i % 1000000007
while t > 0:
	n = int(input())
	print(dp[n + 1] - 1)
	t -= 1


case = int(input())
mod = 1000000007
maxval = 1000004
precomp = [1, 1]
for i in range(2, maxval):
	precomp.append(precomp[-1] * i % mod % mod)
for i in range(case):
	n = int(input())
	print(precomp[n + 1] - 1)


arr = [0] * 1000000
s = 1
arr[0] = s
for i in range(2, 1000000 + 1):
	s = (s + i + s * i) % 1000000007
	arr[i - 1] = s
for _ in range(int(input())):
	print(arr[int(input()) - 1])


l = [1] * 1000005
for j in range(2, 1000001):
	l[j] = (l[j - 1] + j + l[j - 1] * j) % 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	print(l[n])


dp = [1 for i in range(1000002)]
for i in range(2, 1000002):
	dp[i] = i * dp[i - 1] % 1000000007
for _ in range(int(input())):
	n = int(input())
	print((dp[n + 1] - 1) % 1000000007)


MOD = 10 ** 9 + 7
factorial_list = [1 for _ in range(10 ** 6 + 2)]
for i in range(2, 10 ** 6 + 2):
	factorial_list[i] = i * factorial_list[i - 1] % MOD
for _ in range(int(input())):
	n = int(input())
	print((factorial_list[n + 1] - 1) % MOD)


modulo = 10 ** 9 + 7
L = [0]
for i in range(1, 1000001):
	L.append(i)
for i in range(2, 1000001):
	L[i] = (L[i] + L[i - 1] + L[i] * L[i - 1]) % modulo
for _ in range(int(input())):
	N = int(input())
	print(L[N] % modulo)


ans_array = [0] * (10 ** 6 + 1)
num = 1
ans = 0
while num < 10 ** 6:
	ans = num * ans + num + ans
	ans %= 1000000007
	ans_array[num] = ans
	num += 1
tests = int(input())
for i in range(tests):
	num = int(input())
	print(ans_array[num])


(l, r) = ([], 1)
MOD = 10 ** 9 + 7
for i in range(2, 1000001):
	r = r * i % MOD
	l.append(r - 1)
for _ in range(int(input())):
	N = int(input())
	print(l[N - 1])


a = []
for i in range(0, 10 ** 6 + 1):
	a.append(i)
for i in range(2, 10 ** 6 + 1):
	a[i] = (a[i] + a[i - 1] + a[i] * a[i - 1]) % 1000000007
for i in range(int(input())):
	n = int(input())
	print(a[n] % (10 ** 9 + 7))


m = 1000000007
l = [0] * 1000001
for i in range(10 ** 6 + 1):
	l[i] = i
for i in range(2, 10 ** 6 + 1):
	l[i] = (l[i] + l[i - 1] + l[i] * l[i - 1]) % m
for _ in range(int(input())):
	n = int(input())
	print(l[n] % m)


m = 10 ** 9 + 7
l = [1]
for i in range(2, 10 ** 6 + 2):
	l.append(l[-1] % m * (i % m) % m)
for _ in range(int(input())):
	n = int(input())
	print((l[n] - 1) % m)


m = 10 ** 9 + 7
a = [1]
for i in range(2, 10 ** 6 + 2):
	a.append(a[-1] % m * (i % m) % m)
for j in range(int(input())):
	n = int(input())
	print((a[n] - 1) % m)


l = []
s = 1
for i in range(1, 1000002):
	s = s * i % 1000000007
	l.append((s - 1) % 1000000007)
for i in range(int(input())):
	print(l[int(input())])


mod = 10 ** 9 + 7
a = [1]
for i in range(2, 10 ** 6 + 2):
	a.append(a[-1] % mod * (i % mod) % mod)
for testcases in range(int(input())):
	n = int(input())
	print((a[n] - 1) % mod)


l = []
p = 1
for i in range(1, 1000002):
	p = p * i % (10 ** 9 + 7)
	l.append(p - 1)
for tc in range(int(input())):
	print(l[int(input())])


a = 4
b = 3
c = 5
l = [1, 5]
for i in range(2, 1000006):
	c = (c * a + b) % 1000000007
	l.append(c)
	a += 1
	b += 1
t = int(input(''))
for i in range(t):
	n = int(input(''))
	print(l[n - 1])


memo = {1: 1}
for _ in range(int(input())):
	val = 1
	n = int(input())
	if n in memo:
		print(memo[n])
		continue
	for i in range(2, n + 1):
		val = (val + i + val * i) % (10 ** 9 + 7)
		memo[i] = val
	print(val)


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
a = [0, 1]
for i in range(2, 1000001):
	x = a[i - 1]
	y = i
	s = (x % mod + y % mod + x % mod * (y % mod) % mod) % mod
	a.append(s)
for _ in range(ii()):
	print(a[ii()])


n = 1000000
m = 1000000007
arr = [0] * n
for i in range(n):
	arr[i] = i + 1
for i in range(1, n):
	arr[i] = (arr[i] % m + arr[i - 1] + arr[i] % m * arr[i - 1]) % m
T = int(input())
while T > 0:
	n = int(input())
	print(arr[n - 1])
	T -= 1


m = 1000000007
n = 1000000
T = int(input())
array = [0] * n
for i in range(n):
	array[i] = i
for i in range(1, n):
	array[i] = (array[i] + array[i - 1] + array[i] * array[i - 1]) % m
for i in range(T):
	n = int(input())
	print(array[n] % m)


from math import factorial
mod = 1000000007
MAXN = 1000002
fac = [0] * MAXN
fac[0] = 1
for i in range(1, MAXN):
	fac[i] = fac[i - 1] * i % mod
for _ in range(int(input())):
	n = int(input())
	ans = (fac[n + 1] % mod - 1 % mod) % mod
	print(ans % mod)


m = 1000000007
l = [0] * 1000001
for i in range(1000001):
	l[i] = i
for i in range(2, 1000001):
	l[i] = (l[i] + l[i - 1] + l[i] * l[i - 1]) % m
for i in range(int(input())):
	n = int(input())
	print(l[n] % m)


t = int(input())
precompute = [0] * 1000002
precompute[1] = 1
mod = 1000000000.0 + 7
for i in range(2, 1000002):
	precompute[i] = precompute[i - 1] % mod * i % mod % mod
for _ in range(t):
	n = int(input())
	ans = (precompute[n + 1] - 1) % mod
	print(int(ans))


fact = [1] * (10 ** 6 + 2)
mode = 10 ** 9 + 7
for i in range(1, 10 ** 6 + 2):
	fact[i] = fact[i - 1] * i % mode

def solve():
	n = int(input())
	return (fact[n + 1] - 1) % mode
tc = int(input())
for t in range(tc):
	print(solve())


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
q = 1000002
f = [1]
mod = 1000000007
for i in range(1, q):
	f.append(f[-1] * i % mod)
for _ in range(int(input())):
	n = int(input())
	print(f[n + 1] - 1)


q = 1000002
f = [1]
mod = 1000000007
for i in range(1, q):
	f.append(f[-1] * i % mod)
for _ in range(int(input())):
	n = int(input())
	print(f[n + 1] - 1)


M = 1000002
dp = [1]
mod = 1000000007
for i in range(1, M):
	dp.append(dp[-1] * i % mod)
for _ in range(int(input())):
	n = int(input())
	print(dp[n + 1] - 1)


from sys import stdin
m = 10 ** 9 + 7
a = [1]
for i in range(2, 1000005):
	a.append(a[-1] * i % m)
for _ in range(int(stdin.readline())):
	print(a[int(stdin.readline())] - 1)


import math
MAX = 10 ** 6 + 7
MOD = 10 ** 9 + 7
f = [1]
for i in range(2, MAX):
	f.append(f[-1] * i % MOD)
for _ in range(int(input())):
	n = int(input())
	print(f[n] - 1)


t = int(input())
N = [0] * t
for i in range(t):
	N[i] = int(input())
n = max(N)
r = [0] * n
r[0] = 1
val = 1
for i in range(2, n + 1):
	val = (val + i + val * i) % (10 ** 9 + 7)
	r[i - 1] = val
for i in range(t):
	print(r[N[i] - 1] % (10 ** 9 + 7))