A permutation of length N is an array of N integers A = [A_{1}, A_{2}, \dots, A_{N}] such that every integer from 1 to N appears in it exactly once.

We define a function over a permutation as follows:
F(A) = (A_{1} * A_{2}) + (A_{2} * A_{3}) + \cdots + (A_{N-2} * A_{N-1}) + (A_{N-1}*A_{N})

You are given an integer N. What is the expected value of the function F over all possible permutations of length N?

The expected value of the function can be represented as a fraction of the form \frac{P}{Q}. You are required to print P \cdot Q^{-1} \pmod{1 \, 000 \, 000 \, 007}. 

------ Input Format ------ 

- 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 Format ------ 

For each test case, output on a single line the expected value of the function modulo 1 \, 000 \, 000 \, 007.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
2
2
3
----- Sample Output 1 ------ 
2
333333343

----- explanation 1 ------ 
- Test Case $1$: There are $2$ possible permutations: $A = \{1, 2\}$ with $F(A) = 2$ and $A = \{2, 1\}$ with $F(A) = 2$. Hence the expected value of the function is $F(A) = \frac{1}{2} * 2 + \frac{1}{2} * 2 = 2$.

- Test Case $2$: There are $6$ possible permutations, with the value of function as $\{5, 5, 8, 8, 9, 9 \}$. Hence the expected value of the function is $F(A) = \frac{5+5+8+8+9+9}{6} = \frac{22}{3}$. The required output will be $333333343$, since $333333343 \cdot 3 \equiv 22 \pmod {1 \, 000 \, 000 \, 007}$.

Difficulty: VERY_HARD
Tags: Number theory

Combinatorics

Mathematics

Probability

Starter code:

Solutions:
for t in range(int(input())):
	mod = 1000000007
	N = int(input())
	t1 = N * (N + 1) // 2 % mod
	t2 = t1 * t1 % mod
	t3 = N * (N + 1) * (2 * N + 1) // 6 % mod
	t4 = pow(N, mod - 2, mod)
	print(t4 * (t2 - t3) % mod)


t = int(input())
for i in range(t):
	n = int(input())
	c = 1000000007
	s1 = n * (n + 1) // 2 % c
	s2 = s1 * s1 % c
	s3 = n * (n + 1) * (2 * n + 1) // 6 % c
	s4 = pow(n, c - 2, c)
	print(s4 * (s2 - s3) % c)


from fractions import Fraction
for i in range(int(input())):
	n = int(input())
	s = Fraction((n + 1) * (n - 1) * (3 * n + 2), 12)
	z = str(s)
	l = list(z.split('/'))
	a = int(l[0])
	b = 1
	if len(l) == 2:
		b = int(l[1])
	y = pow(b, 1000000005, 1000000007)
	c = a * y % 1000000007
	print(c)


def fastPower(a, b):
	m = b + 2
	r = 1
	while b > 0:
		if b & 1:
			r = r * a % m
		a = a % m * a % m % m
		b >>= 1
	return r % m
m = 1000000007
k2 = fastPower(2, m - 2)
k6 = fastPower(6, m - 2)

def s1(n):
	return n % m * (n + 1) % m % m * k2 % m

def s2(n):
	return n % m * ((n + 1) % m) * ((2 * n + 1) % m) % m * k6 % m

def funcx(n):
	kn = fastPower(n, m - 2)
	ans = (s1(n) % m * s1(n) % m % m + m - s2(n) % m) % m * kn % m
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	print(funcx(n))


def fun(p, q):
	mod = 1000000007
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
t = int(input())
for _ in range(t):
	n = int(input())
	p = (n + 1) * (3 * n * n - n - 2)
	q = 12
	print(fun(p, q))


mod = 1000000007
x = pow(12, mod - 2, mod)

def solve():
	n = int(input())
	ans = (n * n - 1) % mod
	z = (3 * n + 2) % mod
	ans *= z
	ans %= mod
	ans *= x
	ans %= mod
	print(ans)
for iii in range(int(input())):
	solve()


mod = 10 ** 9 + 7
for tc in range(int(input())):
	n = int(input())
	num = (pow(n * (n + 1) // 2, 2, mod) - n * (n + 1) * (2 * n + 1) // 6) % mod
	den = pow(n, mod - 2, mod)
	print(num * den % mod)


import sys
mod = 10 ** 9 + 7

def inverse(a):
	return power(a, mod - 2)

def power(x, y):
	ans = 1
	while y > 0:
		if y & 1:
			ans = ans * x % mod
		x = x * x % mod
		y >>= 1
	return ans

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		n = int(sys.stdin.readline())
		numerator = (power(n * (n + 1) // 2, 2) - n * (n + 1) * (2 * n + 1) // 6) % mod
		denominator = inverse(n)
		answer = numerator * denominator % mod
		print(answer)
main()


T = int(input())
for _ in range(T):
	n = int(input())
	a = (n ** 2 - 1) * (3 * n + 2) % 1000000007
	b = 83333334
	print(a * b % 1000000007)


for n in [*open(0)][1:]:
	n = int(n)
	print(83333334 * (n * n - 1) * (3 * n + 2) % (10 ** 9 + 7))


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
T = int(input())
V = []
while T > 0:
	N = int(input())
	y = N * (N + 1) // 2
	a = (2 * N ** 3 + 3 * N ** 2 + N) // 6
	x = y ** 2 - a
	d = x * modinv(N, 1000000007) % 1000000007
	V.append(int(d))
	T = T - 1
for i in V:
	print(i)


def c(p, q):
	mod = 1000000007
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
for i in range(int(input())):
	n = int(input())
	ans = 3 * n ** 4 + 2 * n ** 3 - 3 * n ** 2 - 2 * n
	print(c(ans // 12, n))


from fractions import Fraction
for _ in range(int(input())):
	n = int(input())
	s = (n - 1) * (Fraction(n * (n - 1), 4) + Fraction(2 * n - 1, 3) + Fraction(1, 2))
	m = 10 ** 9 + 7
	d = pow(s.denominator, m - 2, m)
	res = s.numerator % m * d % m
	print(res)


from fractions import Fraction

def modexp(x, n):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return modexp(x * x % (10 ** 9 + 7), n // 2)
	else:
		return x * modexp(x * x % (10 ** 9 + 7), (n - 1) / 2) % (10 ** 9 + 7)
for _ in range(int(input())):
	n = int(input())
	s = (n - 1) * (Fraction(n * (n - 1), 4) + Fraction(2 * n - 1, 3) + Fraction(1, 2))
	m = 10 ** 9 + 7
	d = modexp(s.denominator, m - 2)
	res = s.numerator % m * (d % m) % m
	print(res)


MOD = 10 ** 9 + 7

def mod_mul(a, b):
	return a % MOD * (b % MOD) % MOD

def mod_sum(a, b):
	return (a + b) % MOD

def mod_inv(a):
	return pow(a, MOD - 2, MOD)
import io, os, sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

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

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def A():
	for _ in range(inp()):
		(N, K) = invr()
		outp(N // K + 1 if N % K else N // K)

def B():
	for _ in range(inp()):
		N = inp()
		A = invr()
		(mn, mx) = (min(A), max(A))
		outp(0 if mn == mx else mx - mn)

def C():
	for _ in range(inp()):
		N = inp()
		A = insr()
		B = insr()
		(ans, equal) = (0, True)
		for i in range(1, N + 1):
			if equal and A[-i] == B[-i]:
				continue
			elif A[-i] > B[-i]:
				equal = True
				continue
			else:
				equal = False
				ans += 1
		outp(ans)

def D():
	pal = [513, 257, 129, 65, 33, 17, 9, 5, 3, 1]
	for _ in range(inp()):
		N = inp()
		ans = []
		for p in pal:
			while N >= p:
				N -= p
				ans.append(p)
			if not N:
				break
		outp(len(ans))
		outlt(ans)
MOD = 10 ** 9 + 7

def mod_mul(a, b):
	return a % MOD * (b % MOD) % MOD

def mod_sum(a, b):
	return (a + b) % MOD

def mod_inv(a):
	return pow(a, MOD - 2, MOD)
import io, os, sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

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

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def A():
	for _ in range(inp()):
		(N, K) = invr()
		outp(N // K + 1 if N % K else N // K)

def B():
	for _ in range(inp()):
		N = inp()
		A = invr()
		(mn, mx) = (min(A), max(A))
		outp(0 if mn == mx else mx - mn)

def C():
	for _ in range(inp()):
		N = inp()
		A = insr()
		B = insr()
		(ans, equal) = (0, True)
		for i in range(1, N + 1):
			if equal and A[-i] == B[-i]:
				continue
			elif A[-i] > B[-i]:
				equal = True
				continue
			else:
				equal = False
				ans += 1
		outp(ans)

def D():
	pal = [513, 257, 129, 65, 33, 17, 9, 5, 3, 1]
	for _ in range(inp()):
		N = inp()
		ans = []
		for p in pal:
			while N >= p:
				N -= p
				ans.append(p)
			if not N:
				break
		outp(len(ans))
		outlt(ans)

def E():
	q_inv = mod_inv(12)
	In = [inp() for _ in range(inp())]
	Out = ((3 * pow(N, 3, MOD) + 2 * pow(N, 2, MOD) - 3 * N - 2) * q_inv % MOD for N in In)
	outplt(Out)
E()


for i in range(int(input())):
	m = 10 ** 9 + 7
	n = int(input())
	s = 0
	s1 = n * (n + 1) // 2
	s = (s1 * s1 - n * (n + 1) * (2 * n + 1) // 6 + m) % m
	print(s * pow(n, m - 2, m) % m)


a = 1000000007
T = int(input())
for _ in range(T):
	n = int(input())
	p = (n ** 2 - 1) * (3 * n + 2) % a
	q = 83333334
	print(p * q % a)


from itertools import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	su = n * (n + 1) * (n - 1) * (3 * n + 2)
	su = su // 24
	su *= 2
	p = 10 ** 9 + 7
	pr = pow(n, p - 2, p)
	su = su * pr
	print(su % p)


def calculate(p, q):
	mod = 1000000007
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
T = int(input())
for i in range(T):
	n = int(input())
	p = 3 * n ** 3 + 2 * (n * n) - 3 * n - 2
	q = 12
	print(calculate(p, q))


import math
t = int(input())

def calculate(p, q):
	mod = 1000000007
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def do(n):
	p = (n - 1) * (n + 1) * (3 * n + 2)
	gc = math.gcd(p, 12)
	print(calculate(p // gc, 12 // gc))
for i in range(t):
	n = int(input())
	do(n)


from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def sub(a, b):
	return (a - b + mod) % mod

def div(a, b):
	return mul(a, pow(b, mod - 2, mod))

def answer():
	v1 = n * (n + 1) // 2
	v2 = n * (n + 1) * (2 * n + 1) // 6
	ans = sub(mul(v1, v1), v2)
	return div(ans, n)
for T in range(int(input())):
	n = int(input())
	print(answer())


def gcd(a, b):
	while a > 0:
		(a, b) = (b % a, a)
	return b

def invfac(x):
	m = 1000000007
	return pow(x, m - 2, m)
for _ in range(int(input())):
	n = int(input())
	ans = -(n * (n - 1)) ** 2 // 2
	ans -= n * (n - 1) * (2 * n - 1) // 3
	ans += n ** 2 * (n + 1) * (n - 1)
	ans //= 2
	xd = n
	temp = gcd(ans, xd)
	ans //= temp
	xd //= temp
	print(ans * invfac(xd) % 1000000007)


def calculate(p, q):
	mod = 1000000007
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
t = int(input())
while t:
	t -= 1
	n = int(input())
	ans = 3 * n ** 3 + 2 * n ** 2 - 3 * n - 2
	print(calculate(ans, 12))


from math import ceil, e, log2, floor, sqrt, gcd
from collections import defaultdict, deque
import sys
import os.path
sys.setrecursionlimit(200000)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r+')
	sys.stdout = open('output.txt', 'w')

def MI():
	return map(int, input().split())

def find(p, q):
	mod = 1000000007
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def solve(testcase):
	n = int(input())
	n1 = n
	r = n * (n + 1) // 2
	sqsum = n * (2 * n + 1) * (n + 1) // 6
	s = r * r - sqsum
	print(find(s, n))
t = int(input())
for _ in range(t):
	solve(_ + 1)


from math import gcd

def calculate(p, q):
	mod = 10 ** 9 + 7
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def reduceFraction(x, y):
	d = gcd(x, y)
	x = x // d
	y = y // d
	return (x, y)
t = int(input())
for _ in range(t):
	n = int(input())
	(p, q) = reduceFraction((n - 1) * (n + 1) * (3 * n + 2), 12)
	print(calculate(p, q))


m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	p = (n + 1) % m * (3 * pow(n, 2, m) - n - 2) % m
	print(p * 83333334 % m)


def calculate(p, q):
	mod = 1000000007
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def calc(n):
	return (n * (n + 1) // 2) ** 2 - n * (n + 1) * (2 * n + 1) // 6
for _ in range(int(input())):
	n = int(input())
	k = calculate(calc(n), n)
	print(k)


import sys
sys.setrecursionlimit(10 ** 9)

def inv(a, mod):
	inverse = pow(a, mod - 2, mod)
	return inverse
m = 10 ** 9 + 7
d = {}

def fac(n):
	global d
	if n < 2:
		return 1
	if n in d:
		return d[n]
	d[n] = n * fac(n - 1) % m
	return d[n]
for _ in range(int(input())):
	n = int(input())
	tot = (n * (n + 1) // 2) ** 2 - n * (n + 1) * (2 * n + 1) // 6
	p = tot % m
	q = n
	print(p * inv(q, m) % m)


mod = 1000000007

def expo(a, b):
	if not b:
		return 1
	v = expo(a, b // 2)
	v = v * v % mod
	if b % 2:
		v = v * a % mod
	return v

def modinv(a, b):
	d = expo(b, mod - 2)
	v = a * d % mod
	return v
for _ in range(int(input())):
	n = int(input())
	v = 3 * n * n - n - 2
	v = (n + 1) * v
	r = modinv(v, 12)
	print(r)