Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Consider an ordered tree with N vertices. Your task is to calculate the expected value of the number of vertices having exactly one child in such tree assuming that it is uniformly chosen from the set of all ordered trees of size N. 

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 

Each testcase contains a single integer N for which you should calculate the answer.

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

For each test case, output a single line containing two integers, which are explained below.
Consider the answer to be a proper fraction P/Q, where gcd(P, Q) = 1. Then your task is to output two integers PQ^{-1} mod 10^{9}+7 and PQ^{-1} mod 10^{9}+9.

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

$1 ≤ T ≤ 10^{5}$
$It is guaranteed that Q will be invertible with respect to both the modulos.$

------ Subtasks ------ 

Subtask #1 (10 points)

$1 ≤ N ≤ 10^{3}$

Subtask #2 (20 points)

$1 ≤ N ≤ 10^{6}$

Subtask #3 (30 points)

$1 ≤ N ≤ 10^{9}$

Subtask #4 (40 points)

$1 ≤ N ≤ 10^{18}$

----- Sample Input 1 ------ 
4

1

2

3

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

1 1

1 1

400000004 200000003
----- explanation 1 ------ 
You can see every possible tree with 1, 2, 3 or 4 vertices on the diagram below.

From this you can see that answers for these inputs are 0/1 = 0, 1/1 = 1, (2+0)/2 = 1 and (3+1+1+1+0)/5 = 6/5 correspondingly.

Difficulty: HARD
Tags: Graph algorithms

Probability

Combinatorics

Number theory

Tree algorithms

Mathematics

Data structures
Skill types: Data structures

Starter code:

Solutions:
def pow1(a, b, mod):
	a %= mod
	if b == 0:
		return 1
	res = pow1(a, b // 2, mod)
	res *= res
	res %= mod
	if b % 2:
		res *= a
	return res % mod
for _ in range(int(input())):
	n = int(input())
	mod1 = int(1000000000.0 + 7)
	mod2 = int(1000000000.0 + 9)
	if n == 1:
		print('0 0')
		continue
	if n <= 3:
		print('1 1')
		continue
	p1 = n * (n - 1) % mod1
	p2 = n * (n - 1) % mod2
	q1 = 2 * (n + n - 3) % mod1
	q2 = 2 * (n + n - 3) % mod2
	inv1 = pow1(q1, mod1 - 2, mod1)
	inv2 = pow1(q2, mod2 - 2, mod2)
	ans1 = p1 * inv1 % mod1
	ans2 = p2 * inv2 % mod2
	print(str(ans1) + ' ' + str(ans2))


def modInverse(a, m):
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
m1 = int(1000000000.0 + 7)
m2 = int(1000000000.0 + 9)
for _ in range(int(input())):
	n = int(input())
	p = n * (n - 1) // 2
	q = 2 * n - 3
	mi = modInverse(q, m1)
	mi2 = modInverse(q, m2)
	print(p * mi % m1, p * mi2 % m2)


from fractions import _gcd
from math import floor, gcd
m1 = 1000000007
m2 = 1000000009

def gcdExtended(a, b):
	if a == 0:
		return [b, 0, 1]
	l = gcdExtended(b % a, a)
	gcd = [l[0], l[2] - b // a * l[1], l[1]]
	return gcd

def modInverse(a, m):
	g = gcdExtended(a, m)
	return (g[1] % m + m) % m
t = int(input())
while t > 0:
	n = int(input())
	x = gcd(n * (n - 1), 4 * n - 6)
	p = n * (n - 1) // x
	q = (4 * n - 6) // x
	ans1 = p % m1 * modInverse(q, m1) % m1
	ans2 = p % m2 * modInverse(q, m2) % m2
	print(ans1, ans2)
	t -= 1


from fractions import Fraction
MOD9 = 10 ** 9 + 9
MOD7 = 10 ** 9 + 7
t = int(input().strip())
while t:
	n = int(input().strip())
	num = n * (n - 1)
	den = 4 * n - 6
	a = Fraction(num, den)
	inv = pow(a.denominator, MOD7 - 2, MOD7)
	ans = a.numerator % MOD7 * inv % MOD7
	print(ans, end=' ')
	inv = pow(a.denominator, MOD9 - 2, MOD9)
	ans = a.numerator % MOD9 * inv % MOD9
	print(ans)
	t -= 1


from fractions import gcd
a = int(input())
for i in range(a):
	n = int(input())
	atas = n * (n - 1)
	bawah = 4 * n - 6
	g = gcd(atas, bawah)
	atas //= g
	bawah //= g
	md = 1000000007
	md2 = 1000000009
	bawah1 = pow(bawah, md - 2, md)
	bawah2 = pow(bawah, md2 - 2, md2)
	print(atas * bawah1 % md, atas * bawah2 % md2)


import fractions
t = int(input())
for i in range(t):
	k = int(input())
	numer = k * (k - 1)
	denomi = 4 * k - 6
	ti = fractions.gcd(numer, denomi)
	numer = numer // ti
	denomi = denomi // ti
	m1 = 1000000007
	m2 = 1000000009
	yt = pow(denomi, m1 - 2, m1)
	sg = pow(denomi, m2 - 2, m2)
	s1 = numer * yt
	s2 = numer * sg
	print(s1 % m1, s2 % m2)


def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
t = int(input())
for i in range(t):
	n = int(input())
	p = n * (n - 1) // 2
	q = 2 * n - 3
	q1 = modinv(q, 1000000007)
	q2 = modinv(q, 1000000009)
	ans1 = p % 1000000007 * (q1 % 1000000007) % 1000000007
	ans2 = p % 1000000009 * (q2 % 1000000009) % 1000000009
	print(ans1, ans2)


import math
import fractions

def lis(a):
	l = []
	l.append(n * n - n)
	l.append(2 * (2 * n - 3))
	l.append(l[0] // fractions.gcd(l[0], l[1]))
	l.append(l[1] // fractions.gcd(l[0], l[1]))
	return l

def ans(num):
	a1 = pow(num[3], 1000000000 + 7 - 2, 1000000000 + 7)
	a2 = pow(num[3], 1000000000 + 9 - 2, 1000000000 + 9)
	print(a1 * num[2] % (1000000000 + 7), a2 * num[2] % (1000000000 + 9))
t = eval(input())
for i in range(t):
	n = eval(input())
	num = lis(n)
	ans(num)


from fractions import gcd
mod1 = 1000000007
mod2 = 1000000009

def comp(n):
	if n == 1:
		return [0, 0]
	else:
		num = n * (n - 1)
		den = 2 * (2 * n - 3)
		g = gcd(num, den)
		num = num // g
		den = den // g
		return [num % mod1 * pow(den, mod1 - 2, mod1) % mod1, num % mod2 * pow(den, mod2 - 2, mod2) % mod2]
t = int(input())
for i in range(t):
	n = int(input())
	res = comp(n)
	print(res[0], res[1])


import sys
PRM1 = 1000000007
PRM2 = 1000000009

def main():
	t = int(sys.stdin.readline())
	while t > 0:
		n = int(sys.stdin.readline())
		expTree(n - 1)
		t -= 1

def expTree(n):
	p = n * (n + 1)
	q = 2 * (2 * n - 1)
	x = gcd(p, q)
	if x != 1:
		p //= x
		q //= x
	ans1 = p % PRM1 * (inverse(q, PRM1) % PRM1) % PRM1
	ans2 = p % PRM2 * (inverse(q, PRM2) % PRM2) % PRM2
	print(ans1, end=' ')
	print(ans2)

def inverse(q, m):
	return power(q, m - 2, m)

def power(a, b, m):
	if b == 0:
		return 1
	p = power(a, b // 2, m)
	p = p * p % m
	if b % 2 == 0:
		return p
	else:
		return a * p % m

def gcd(p, q):
	if p == 0:
		return q
	return gcd(q % p, p)
main()


def lulz(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

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
counter = int(input())
for mrinal in range(counter):
	a = int(input())
	n = a - 1
	if n == 0:
		print(0, 0)
		continue
	p = n * (n + 1)
	q = 2 * (2 * n - 1)
	f = lulz(p, q)
	p = p // f
	q = q // f
	s = p % 1000000007 * pow_mod(q, 1000000007 - 2, 1000000007) % 1000000007
	t = p % 1000000009 * pow_mod(q, 1000000009 - 2, 1000000009) % 1000000009
	print(s, t)


from fractions import gcd
(M1, M2) = (10 ** 9 + 7, 10 ** 9 + 9)
T = int(input().strip())
while T:
	T -= 1
	N = int(input().strip())
	x = N // 2 * (N - 1) if N % 2 == 0 else N * ((N - 1) // 2)
	y = 2 * N - 3
	g = gcd(x, y)
	(x, y) = (x // g, y // g)
	print(x % M1 * pow(y, M1 - 2, M1) % M1, x % M2 * pow(y, M2 - 2, M2) % M2)


import fractions
md7 = 10 ** 9 + 7
md9 = 10 ** 9 + 9
t = int(input())
for _ in range(t):
	n = int(input()) - 1
	a = n * (n + 1)
	b = 2 * (2 * n - 1)
	c = fractions.gcd(a, b)
	a //= c
	b //= c
	ans7 = a * pow(b, md7 - 2, md7) % md7
	ans9 = a * pow(b, md9 - 2, md9) % md9
	print(ans7, ans9)


from fractions import gcd
from fractions import Fraction as fr
t = int(input())
while t > 0:
	n = int(input())
	n = n - 1
	p = n * (n + 1)
	q = 4 * n - 2
	p1 = p
	q1 = q
	p = fr(p1, q1).numerator
	q = fr(p1, q1).denominator
	if n == 0 or p <= 0 or q <= 0:
		print(str(0) + ' ' + str(0))
		t = t - 1
		continue
	qinv1 = pow(q, 10 ** 9 + 5, 10 ** 9 + 7)
	res1 = p * qinv1 % (10 ** 9 + 7)
	qinv2 = pow(q, 10 ** 9 + 7, 10 ** 9 + 9)
	res2 = p * qinv2 % (10 ** 9 + 9)
	print(str(res1) + ' ' + str(res2))
	t = t - 1


m1 = 1000000007
m2 = 1000000009
t = int(input())

def modpow(base, exp, modulus):
	base %= modulus
	result = 1
	while exp > 0:
		if exp & 1:
			result = result * base % modulus
		base = base * base % modulus
		exp = exp // 2
	return result

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for i in range(t):
	n = int(input())
	p = n * (n - 1)
	q = 2 * (2 * n - 3)
	g = gcd(p, q)
	(p, q) = (p // g, q // g)
	ans1 = modpow(q, m1 - 2, m1) * p % m1
	ans2 = modpow(q, m2 - 2, m2) * p % m2
	print(ans1, ans2)


def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def is_prime(n):
	if n == 2 or n == 3:
		return True
	if n < 2 or n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		print(f)
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 6
	return True

def is_prime(n):
	if n < 2:
		return False
	if n % 2 == 0:
		return n == 2
	k = 3
	while k * k <= n:
		if n % k == 0:
			return False
		k += 2
	return True

def sort(array=[12, 4, 5, 6, 7, 3, 1, 15]):
	less = []
	equal = []
	greater = []
	if len(array) > 1:
		pivot = array[0]
		for x in array:
			if x < pivot:
				less.append(x)
			if x == pivot:
				equal.append(x)
			if x > pivot:
				greater.append(x)
		return sort(less) + equal + sort(greater)
	else:
		return array
from fractions import Fraction
for _ in range(int(input())):
	n = int(input())
	p = n * (n - 1)
	q = 4 * n - 6
	p = Fraction(n * (n - 1), 4 * n - 6).numerator
	q = Fraction(n * (n - 1), 4 * n - 6).denominator
	if n == 1:
		print(str(0) + ' ' + str(0))
		continue
	a = pow(q, 10 ** 9 + 5, 10 ** 9 + 7)
	b = pow(q, 10 ** 9 + 7, 10 ** 9 + 9)
	print(str(p * a % (10 ** 9 + 7)) + ' ' + str(p * b % (10 ** 9 + 9)))


Mx = 10 ** 9 + 7
My = 10 ** 9 + 9
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print('0 0')
	else:
		N = N - 1
		X1 = (N * (N + 1) >> 1) % Mx
		X2 = (N * (N + 1) >> 1) % My
		Y1 = pow(2 * N - 1, Mx - 2, Mx)
		Y2 = pow(2 * N - 1, My - 2, My)
		skx = X1 * Y1 % Mx
		sky = X2 * Y2 % My
		print(skx, sky, sep=' ')


import fractions

def cat(n):
	if n is 1:
		return [0, 0]
	n -= 1
	x = n * (n + 1)
	y = 2 * (2 * n - 1)
	h = fractions.gcd(x, y)
	return [x // h, y // h]
T = int(input())
z = 0
while z < T:
	z += 1
	i = int(input())
	(P, Q) = cat(i)
	x = P % (10 ** 9 + 7)
	y = pow(Q, 10 ** 9 + 5, 10 ** 9 + 7)
	print(x * y % (10 ** 9 + 7), end='')
	print(' ', end='')
	x = P % (10 ** 9 + 9)
	y = pow(Q, 10 ** 9 + 7, 10 ** 9 + 9)
	print(x * y % (10 ** 9 + 9))


MOD1 = 10 ** 9 + 7
MOD2 = 10 ** 9 + 9
tc = int(input())

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

def binpow(a, b, MOD):
	if b == 0:
		return 1
	if b % 2 == 0:
		z = binpow(a, b // 2, MOD)
		return z * z % MOD
	return a * binpow(a, b - 1, MOD) % MOD
for _ in range(tc):
	n = int(input())
	n -= 2
	nom = (1 + n) * (1 + n) * (2 + n)
	den = (2 * n + 2) * (2 * n + 1)
	if n == -1:
		print('0 0')
		continue
	k = gcd(nom, den)
	nom //= k
	den //= k
	print(nom * binpow(den, MOD1 - 2, MOD1) % MOD1, nom * binpow(den, MOD2 - 2, MOD2) % MOD2)


from fractions import Fraction

def find():
	n = int(input())
	if n == 1:
		print(0, 0)
		return
	ans = Fraction((n - 1) * n, 2 * (2 * n - 3))
	m = 10 ** 9 + 7
	m1 = 10 ** 9 + 9
	print(ans.numerator * pow(ans.denominator, m - 2, m) % m, ans.numerator * pow(ans.denominator, m1 - 2, m1) % m1)
t = int(input())
for i in range(t):
	find()


mod1 = 1000000007
mod2 = 1000000009

def binomial(n, r):
	if r > n - r:
		r = n - r
	res = 1
	for i in range(r):
		res = res * (n - i)
		res = res // (i + 1)
	return res

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

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

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

def catalan(c, n):
	return c // (n + 1)
t = int(input())
for y in range(t):
	n = int(input()) - 1
	p = n * (n + 1)
	q = 2 * (2 * n - 1)
	print(p * inverse(q, mod1) % mod1, p * inverse(q, mod2) % mod2)


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

def invmod(x, y):
	(a, b, c) = ext_gcd(x, y)
	if a != 1:
		raise Exception('fuck')
	else:
		return b % y
for _ in range(int(input())):
	n = int(input())
	n = n - 1
	if n == 0:
		print('0 0')
	else:
		num = n * (n + 1)
		den = 4 * n - 2
		MOD1 = 1000000007
		MOD2 = 1000000009
		x = invmod(den, MOD1)
		y = invmod(den, MOD2)
		print(num * x % MOD1, num * y % MOD2)


def fast_pow(base, n, M):
	if n == 0:
		return 1
	if n == 1:
		return base
	half = fast_pow(base, n // 2, M)
	if n % 2 == 0:
		return half * half % M
	else:
		return half * half % M * base % M

def findMMI_fermat(n, M):
	return fast_pow(n, M - 2, M)
M = 1000000007
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(0, 0)
	else:
		a = n % M * ((n - 1) % M) % M
		b = ((n % M << 2) % M - 6) % M
		print(a * findMMI_fermat(b, M) % M, end=' ')
		M += 2
		a = n % M * ((n - 1) % M) % M
		b = ((n % M << 2) % M - 6) % M
		print(a * findMMI_fermat(b, M) % M)
		M -= 2


import sys
sys.setrecursionlimit(10000000)
m1 = 1000000007
m2 = 1000000009

def mod_inv(q, m):
	(g, x, junk) = gcd(q, m)
	if g == 1:
		return x % m

def gcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, x, y) = gcd(b % a, a)
	return (g, y - b // a * x, x)
t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print('0 0')
		continue
	p = n * (n - 1)
	q = 2 * (2 * n - 3)
	g = gcd(p, q)[0]
	p = p // g
	q = q // g
	print(str(p * mod_inv(q, m1) % m1), str(p * mod_inv(q, m2) % m2))


MOD1 = 10 ** 9 + 7
MOD2 = 10 ** 9 + 9

def mod_exp_inv(base, expo, md):
	base = base % md
	ans = 1
	while expo > 0:
		if expo & 1:
			ans = ans * base % md
		base = base * base % md
		expo //= 2
	return ans % md

def gcd_euclid(x, y):
	if x == 0 and y == 0:
		return -1
	while y:
		(x, y) = (y, x % y)
	return x

def solve_tr(n):
	if n == 1:
		print('0 0')
		return
	p = n * (n - 1)
	q = 4 * n - 6
	gcd_pq = gcd_euclid(p, q)
	p1 = p // gcd_pq % MOD1
	q1 = q // gcd_pq % MOD1
	p2 = p // gcd_pq % MOD2
	q2 = q // gcd_pq % MOD2
	res1 = p1 * mod_exp_inv(q1, MOD1 - 2, MOD1) % MOD1
	res2 = p2 * mod_exp_inv(q2, MOD2 - 2, MOD2) % MOD2
	print(str(res1) + ' ' + str(res2))
	return
t = int(input())
for _ in range(t):
	n = int(input())
	solve_tr(n)


from fractions import gcd
MOD1 = 1000000007
MOD2 = MOD1 + 2

def modinverse(num, mod):
	m = mod
	(a, b) = (0, 1)
	if mod == 1:
		return 0
	while num >= 2:
		(q, tmp) = (num // mod, mod)
		mod = num % mod
		num = tmp
		tmp = a
		(a, b) = (b - q * a, tmp)
	if b < 0:
		b = b + m
	return b
for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(n - 1, n - 1)
	elif n == 3:
		print(1, 1)
	else:
		(p, q) = ((n - 1) * n, 4 * n - 6)
		gc = gcd(p, q)
		(p, q) = (p // gc, q // gc)
		(x, y) = (modinverse(q, MOD1), modinverse(q, MOD2))
		(x, y) = (p * x % MOD1, p * y % MOD2)
		print(x, y)


t = int(input())
for j in range(t):
	n = int(input())
	x = 1000000000 + 7
	y = 1000000000 + 9
	p = n * (n - 1)
	p = p // 2
	q = 2 * n - 3
	a1 = p % x
	q1 = pow(q, x - 2, x)
	b1 = a1 * q1 % x
	a2 = p % y
	q2 = pow(q, y - 2, y)
	b2 = a2 * q2 % y
	print(b1, b2)


import math

def gcd(x, y, flag=True):
	if x < y:
		return gcd(y, x, flag)
	while y != 0:
		(x, y) = (y, x % y)
	return x

def inverse(a, b):
	s1 = 0
	s = 1
	r1 = b
	r = a
	while r1 != 0:
		q = math.floor(r / r1)
		(r, r1) = (r1, r - q * r1)
		(s, s1) = (s1, s - q * s1)
	return s

def inverse_mod(a, m):
	x = inverse(a, m)
	if x < 0:
		x += m
	return x
test = eval(input())
for t in range(test):
	n = eval(input())
	n = n - 1
	a = n * (n + 1)
	b = 2 * (2 * n - 1)
	in2 = inverse_mod(b, 1000000007)
	ans = a * in2 % 1000000007
	in1 = inverse_mod(b, 1000000009)
	ans1 = a * in1 % 1000000009
	print(ans, ans1)


import fractions

def alli(n):
	if n is 1:
		return [0, 0]
	n -= 1
	a = n * (n + 1)
	b = 2 * (2 * n - 1)
	g = fractions.gcd(a, b)
	return [a // g, b // g]
T = int(input())
z = 0
while z < T:
	z += 1
	i = int(input())
	(P, Q) = alli(i)
	a = P % (10 ** 9 + 7)
	b = pow(Q, 10 ** 9 + 5, 10 ** 9 + 7)
	print(a * b % (10 ** 9 + 7), end='')
	print(' ', end='')
	a = P % (10 ** 9 + 9)
	b = pow(Q, 10 ** 9 + 7, 10 ** 9 + 9)
	print(a * b % (10 ** 9 + 9))


MOD1 = 1000000007
MOD2 = 1000000009

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

def inMod(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1
T = int(input())
for t in range(T):
	n = int(input())
	if n == 1:
		print(0, 0)
		continue
	n -= 1
	P = n * (n + 1)
	Q = 2 * (2 * n - 1)
	f = gcd(P, Q)
	P //= f
	Q //= f
	print(P * inMod(Q, MOD1) % MOD1, P * inMod(Q, MOD2) % MOD2)


import fractions
a = input()
for i in range(1, int(a) + 1):
	n = input()
	n = int(n)
	den = 2 * (2 * n - 3)
	num = n * (n - 1)
	g = fractions.gcd(num, den)
	num = num // g
	den = den // g
	b = pow(den, 1000000005, 1000000007)
	b = b * num % 1000000007
	print(b, '', end='')
	b = pow(den, 1000000007, 1000000009)
	b = b * num % 1000000009
	print(b)


def ReduceFrac(m, n):
	while m > 0:
		x = m
		m = n % m
		n = x
	return n

def pow(a, b, MOD):
	x = 1
	y = a
	while b > 0:
		if b % 2 == 1:
			x = x * y
			if x > MOD:
				x = x % MOD
		y = y * y
		if y > MOD:
			y = y % MOD
		b = b // 2
	return x
tc = int(input())
for t in range(tc):
	n = int(input())
	if n == 1:
		p = 0
		q = 0
		gcd = 1
		print(p, q)
	else:
		p = n
		q = 2 * n - 3
		gcd = ReduceFrac(p, q)
		p = p // gcd
		q = q // gcd
		a = n - 1
		gcd1 = ReduceFrac(a, q)
		a = a // gcd1
		q = q // gcd1
		p = p * a // 2
		c = pow(q, 1000000005, 1000000007)
		d = p % 1000000007 * (c % 1000000007) % 1000000007
		e = pow(q, 1000000007, 1000000009)
		f = p % 1000000009 * (e % 1000000009) % 1000000009
		print(d, f)


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

def inversemod(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 = x1 + m0
	return x1
t = int(input())
for _ in range(t):
	mod1 = 1000000007
	mod2 = 1000000009
	n = int(input())
	u = n * (n - 1)
	l = 2 * (2 * n - 3)
	m = gcd(u, l)
	u = u // m
	l = l // m
	l1 = inversemod(l, mod1)
	l2 = inversemod(l, mod2)
	print(u % mod1 * (l1 % mod1) % mod1, u % mod2 * (l2 % mod2) % mod2)


def power(x, y, m):
	if y == 0:
		return 1
	p = power(x % m, y // 2, m) % m
	p = p % m * p % m % m
	if y % 2 == 0:
		return p % m
	else:
		return x % m * p % m % m

def modInverse(a, m):
	return power(a % m, m - 2, m)

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

def findans(n, m):
	if n % m == 0 or (n - 1) % m == 0:
		return 0
	q = 4 * n - 6
	common = gcd(n, q)
	p = n // common % m
	q = q // common
	common = gcd(n - 1, q)
	p = p * ((n - 1) // common) % m % m
	q = q // common
	q = modInverse(q, m)
	return p % m * q % m % m
M1 = 1000000007
M2 = 1000000009
t = int(input())
for i in range(t):
	n = int(input())
	print(str(findans(n, M1)) + ' ' + str(findans(n, M2)))


MOD1 = 10 ** 9 + 7
MOD2 = 10 ** 9 + 9

def modPow(base, power, modulus):
	ans = 1
	tmp = base
	p = power
	while p > 0:
		if p & 1 != 0:
			ans = ans * tmp % modulus
		tmp = tmp * tmp % modulus
		p >>= 1
	return ans

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

def inv(n, modulus):
	return modPow(n, modulus - 2, modulus)
nTests = int(input())
for _ in range(nTests):
	n = int(input())
	n = n - 1
	numNodesWithOneChild = n * n + n
	numTrees = 4 * n - 2
	d = gcd(numTrees, numNodesWithOneChild)
	numTrees //= d
	numNodesWithOneChild //= d
	ans1 = numNodesWithOneChild * inv(numTrees, MOD1) % MOD1
	ans2 = numNodesWithOneChild * inv(numTrees, MOD2) % MOD2
	print(ans1, ans2)


from fractions import gcd
m1 = int(1000000007)
m2 = int(1000000009)

def GCD(a, b):
	if b == 0:
		return int(a)
	else:
		return int(GCD(b, a % b))

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())
for i in range(0, t):
	n = int(input())
	if n == 1:
		print('0 0')
		continue
	if n == 2 or n == 3:
		print('1 1')
		continue
	p = int(n * (n - 1))
	q = int(2 * (2 * n - 3))
	var = int(GCD(int(p), int(q)))
	p = int(p // var)
	q = int(q // var)
	q1 = int(modinv(q, m1))
	x = int(p % m1 * q1 % m1 % m1)
	q2 = int(modinv(q, m2))
	y = int(p % m2 * q2 % m2 % m2)
	print(x, end=' ')
	print(y)


def mod_exp(a, b, m):
	if b == 0:
		return 1
	ans = mod_exp(a, b // 2, m) % m
	ans = ans * ans % m
	if b % 2 == 0:
		return ans
	else:
		return a * ans % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
mod1 = int(1000000007)
mod2 = int(1000000009)
t = int(input())
for i in range(t):
	n = int(input())
	num = n * (n - 1)
	den = 2 * (2 * n - 3)
	g = int(gcd(num, den))
	num = num // g
	den = den // g
	a1 = num % mod1 * mod_exp(den, mod1 - 2, mod1) % mod1
	a2 = num % mod2 * mod_exp(den, mod2 - 2, mod2) % mod2
	print(a1, a2)


M1 = 10 ** 9 + 7
M2 = 10 ** 9 + 9
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print('0 0')
	else:
		N = N - 1
		X1 = (N * (N + 1) >> 1) % M1
		X2 = (N * (N + 1) >> 1) % M2
		Y1 = pow(2 * N - 1, M1 - 2, M1)
		Y2 = pow(2 * N - 1, M2 - 2, M2)
		R1 = X1 * Y1 % M1
		R2 = X2 * Y2 % M2
		print(R1, R2, sep=' ')


def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def modinverse(a, m):
	return power(a, m - 2, m)
t = int(input())
first = 1000000007
secon = 1000000009
for _ in range(t):
	n = int(input())
	if n == 1:
		print(0, 0)
	else:
		q1 = ((n - 1) * 2 - 1) * 2 % first
		p1 = n % first * ((n - 1) % first)
		q2 = ((n - 1) * 2 - 1) * 2 % secon
		p2 = n % secon * ((n - 1) % secon)
		a1 = p1 % first * (modinverse(q1, first) % first) % first
		a2 = p2 % secon * (modinverse(q2, secon) % secon) % secon
		print(a1, a2)


t = int(input())
m1 = 10 ** 9 + 7
m2 = 10 ** 9 + 9

def gcd(a1, a2):
	if a1 == 0:
		return a2
	return gcd(a2 % a1, a1)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m)
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def modular(a1, m):
	return power(a1, m - 2, m)
for i in range(t):
	n = int(input())
	a = n * (n - 1)
	b = 2 * (2 * n - 3)
	c = gcd(a, b)
	a //= c
	b //= c
	print(a % m1 * modular(b, m1) % m1, a % m2 * modular(b, m2) % m2)


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

def main():
	t = int(input(''))
	while t > 0:
		n = int(input(''))
		if n == 1:
			print('0 0')
		elif n == 2:
			print('1 1')
		else:
			num1 = n * (n - 1) % 1000000007
			den1 = den2 = 4 * n - 6
			num2 = n * (n - 1) % 1000000009
			print('{} {}'.format(num1 * power(den1, 1000000005, 1000000007) % 1000000007, num2 * power(den2, 1000000007, 1000000009) % 1000000009))
		t = t - 1
main()


md1 = 10 ** 9 + 7
md2 = 10 ** 9 + 9

def mdinv(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		quo = a // m
		temp = m
		m = a % m
		a = temp
		temp = x0
		x0 = x1 - quo * x0
		x1 = temp
	if x1 < 0:
		x1 += m0
	return x1

def gcd(n1, n2):
	if n2:
		return gcd(n2, n1 % n2)
	else:
		return n1
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print('0 0')
		continue
	if n == 2 or n == 3:
		print('1 1')
		continue
	n -= 1
	num = n * (n + 1)
	den = 4 * n - 2
	x = gcd(num, den)
	num = num // x
	den = den // x
	a = mdinv(den, md1)
	b = mdinv(den, md2)
	print(num * a % md1, num * b % md2)


def inverse(a, b, mod):
	return a * pow(b, mod - 2, mod) % mod
t = int(input())
for _ in range(t):
	n = int(input())
	f1 = n * (n - 1) * (n - 1)
	f2 = (2 * n - 2) * (2 * n - 3)
	ans1 = inverse(f1, f2, 1000000007)
	ans2 = inverse(f1, f2, 1000000009)
	print(ans1, ans2)


import math

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

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	return x * p % m
t = int(input())
while t:
	t -= 1
	n = int(input())
	if n == 1:
		(num, denom) = (0, 1)
	elif n == 2:
		num = denom = 1
	else:
		num = n * (n - 1) * (n - 1)
		denom = (2 * n - 2) * (2 * n - 3)
	g = gcd(num, denom)
	num //= g
	denom //= g
	print(num * power(denom, 1000000005, 1000000007) % 1000000007, num * power(denom, 1000000007, 1000000009) % 1000000009)


def power(a, n, mod):
	if n <= 0:
		return 1
	elif n == 1:
		return a
	else:
		p = power(a, n // 2, mod)
		p = p * p % mod
		if n % 2 == 1:
			p = p * a % mod
		return p
mod1 = 1000000007
mod2 = 1000000009
for i in range(int(input())):
	n = int(input())
	num = n * (n - 1) // 2
	den = 2 * n - 3
	den1 = power(den, mod1 - 2, mod1)
	den2 = power(den, mod2 - 2, mod2)
	ans1 = num * den1 % mod1
	ans2 = num * den2 % mod2
	print(ans1, ans2)


def gc(e, r):
	if r == 0:
		return e
	else:
		return gc(r, e % r)

def binaryExp1(x1, n):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return binaryExp1(x1 * x1 % 1000000007, n // 2)
	else:
		return x1 * binaryExp1(x1 * x1 % 1000000007, (n - 1) // 2) % 1000000007

def binaryExp2(x2, n):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return binaryExp2(x2 * x2 % 1000000009, n // 2)
	else:
		return x2 * binaryExp2(x2 * x2 % 1000000009, (n - 1) // 2) % 1000000009
import math
t = int(input())
while t > 0:
	a = int(input())
	if a == 1:
		tree = 1
		vertix = 0
	else:
		vertix = a * a - a
		tree = 4 * a - 6
	fraction = gc(tree, vertix)
	tree = tree // fraction
	vertix = vertix // fraction
	m1 = 1000000007
	m2 = 1000000009
	res1 = binaryExp1(tree, m1 - 2) % m1
	res2 = binaryExp2(tree, m2 - 2) % m2
	ans1 = vertix % 1000000009 * res2 % 1000000009
	ans2 = vertix % 1000000007 * res1 % 1000000007
	print(ans2, ans1)
	t = t - 1


from fractions import gcd

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

def modular_inverse(no, mod):
	(g, a, b) = function1(no, mod)
	if g == 1:
		return a % mod
T = int(input())
for t in range(T):
	N = int(input())
	numerator = int(pow(N, 2) - N)
	denominator = 4 * N - 6
	GCD = gcd(numerator, denominator)
	numerator = numerator // GCD
	denominator = denominator // GCD
	inv1 = pow(denominator, 1000000005, 1000000007)
	inv2 = pow(denominator, 1000000007, 1000000009)
	print(int(numerator * inv1 % 1000000007), end='')
	print(' ', end='')
	print(int(numerator * inv2 % 1000000009))


def powermod(a, b, n):
	if b == 1:
		return a % n
	if b == 0:
		return 1
	r = powermod(a, b // 2, n)
	r = r * r % n
	if b % 2 == 1:
		r = r * a % n
	return r
mod1 = 1000000007
mod2 = 1000000009
for _ in range(int(input())):
	n = int(input())
	n = n - 2
	if n == -1:
		print('0 0')
	else:
		nume = (n + 1) * (n + 2) // 2
		deno = 2 * n + 1
		deno1 = powermod(deno, mod1 - 2, mod1)
		deno2 = powermod(deno, mod2 - 2, mod2)
		ans1 = nume * deno1 % mod1
		ans2 = nume * deno2 % mod2
		print(ans1, ans2)


def gcd(aa, bb):
	(lr, r) = (abs(aa), abs(bb))
	(x, lx, y, ly) = (0, 1, 1, 0)
	while r:
		(lr, (q, r)) = (r, divmod(lr, r))
		(x, lx) = (lx - q * x, x)
		(y, ly) = (ly - q * y, y)
	return (lr, lx * (-1 if aa < 0 else 1), ly * (-1 if bb < 0 else 1))

def mi(a, m):
	(g, x, y) = gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m

def HCF(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
from math import factorial, sqrt
for i in range(int(input())):
	n = int(input()) - 1
	if n == 0:
		a = 0
		b = 1
	else:
		a = n * (n + 1)
		b = 4 * n - 2
	p = 10 ** 9 + 7
	q = 10 ** 9 + 9
	z = HCF(a, b)
	a = a // z
	b = b // z
	b1 = mi(b, p)
	b2 = mi(b, q)
	print(a % p * b1 % p % p, a % q * b2 % q % q)


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)
	return x % m
t = int(input())
while t:
	n = int(input())
	n -= 1
	if not n:
		print('0 0')
		t -= 1
		continue
	m = 1000000007
	m2 = 1000000009
	n1 = n % m
	n2 = n % m2
	a1 = n1 * (n1 + 1) % m
	b1 = (4 * n1 - 2) % m
	a2 = n2 * (n2 + 1) % m2
	b2 = (4 * n2 - 2) % m2
	print(int(modinv(b1, m) * a1 % m), int(modinv(b2, m2) * a2 % m2))
	t -= 1


mod = 1000000007
mod2 = 1000000009

def f(x, e, m):
	X = x
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
t = int(input())
for i in range(t):
	n = int(input())
	ans1 = (n - 1) % mod * n % mod * f(4 * n - 6, mod - 2, mod) % mod
	ans2 = (n - 1) % mod2 * n % mod2 * f(4 * n - 6, mod2 - 2, mod2) % mod2
	print(ans1, ans2)


import operator as op
from functools import reduce
import sys
import math

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())
mod1 = 1000000007
mod2 = 1000000009
for i in range(t):
	n = int(input())
	n = n - 1
	if n == 0:
		print('0', ' ', '0')
		continue
	p = (n + 1) * n
	q = (2 * n - 1) * 2
	q1 = modinv(q, mod1)
	q2 = modinv(q, mod2)
	ans1 = (n % mod1 + 1) % mod1 * (n % mod1) % mod1 * (q1 % mod1) % mod1
	ans1 = int(ans1)
	ans2 = (n % mod2 + 1) % mod2 * (n % mod2) % mod2 * (q2 % mod2) % mod2
	ans2 = int(ans2)
	print(ans1, ' ', ans2)


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x

def modinv(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1
modi = 1000000007
modx = 1000000009
t = int(input())
for i in range(t):
	n = int(input())
	n -= 1
	if n == 0:
		print('0 0')
	else:
		a = n * n * (n + 1) % modi
		b = 2 * n * (2 * n - 1)
		e = modinv(b, modi)
		ans1 = a * e % modi
		a = n * n * (n + 1) % modx
		e = modinv(b, modx)
		ans2 = a * e % modx
		print(int(ans1), end=' ')
		print(int(ans2))


MOD = 1000000000 + 7
MOD1 = 1000000000 + 7
MOD2 = 1000000000 + 9

def pow(b, e, m=MOD):
	res = 1
	b = b % m
	while e > 0:
		if e % 2 == 1:
			res = res * (b % m) % m
		b = b * (b % m) % m
		e = e // 2
	return res

def mod_inv(n, m=MOD):
	if n == 2:
		if m == MOD1:
			return 500000004
		elif m == MOD2:
			return 500000005
	return pow(n, m - 2, m)

def num(x, mod):
	return (x % mod * x % mod % mod - x % mod + mod) % mod * mod_inv(2, mod) % mod

def den(x, mod):
	return (2 * x % mod - 3 % mod + mod) % mod
T = int(input())
for t in range(T):
	N = int(input())
	if N == 1:
		print('0 0')
	else:
		ans1 = num(N, MOD1) * mod_inv(den(N, MOD1), MOD1) % MOD1
		ans2 = num(N, MOD2) * mod_inv(den(N, MOD2), MOD2) % MOD2
		print('%d %d' % (ans1, ans2))


M = lambda A, n, s=1, t=0, N=0: (n < 2 and t % N or M(n, A % n, t, s - A // n * t, N or n), -1)[n < 1]
t = int(input())
for i in range(t):
	n1 = int(input())
	if n1 == 1:
		print('0 0')
	elif n1 == 2 or n1 == 3:
		print('1 1')
	else:
		n = n1 * (n1 - 1) * (n1 - 1)
		d = (2 * n1 - 2) * (2 * n1 - 3)
		a = n
		b = d
		r = 0
		while b != 0:
			(a, b) = (b, a % b)
		n = n // a
		d = d // a
		s = 1
		m1 = 1000000007
		m2 = 1000000009
		si = str(n % m1 * M(d, m1) % m1) + ' ' + str(n % m2 * M(d, m2) % m2)
		print(si)


from fractions import gcd
t = int(input())
for i in range(t):
	n = int(input())
	p = n * (n - 1) // 2
	q = 2 * n - 3
	m1 = 1000000007
	m2 = 1000000009
	x = gcd(p, q)
	p = p // x
	q = q // x
	ans1 = p * pow(q, m1 - 2, m1) % m1
	ans2 = p * pow(q, m2 - 2, m2) % m2
	print(str(ans1) + ' ' + str(ans2))


mod1 = 1000000007
mod2 = 1000000009

def power(a, b, m):
	ans = 1
	while b:
		if b % 2 == 1:
			ans = ans * a % m
		a = a * a % m
		b = b // 2
	return ans

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

def lol(n):
	x = (2 * n - 2) * (2 * n - 3)
	y = (n - 1) * (n - 1)
	z = y * n
	g = gcd(x, z)
	x //= g
	z //= g
	print(z * power(x, mod1 - 2, mod1) % mod1, z * power(x, mod2 - 2, mod2) % mod2)
t = int(input())
for _ in range(t):
	n = int(input())
	if n <= 3:
		if n == 1:
			print(0, 0)
		elif n == 2 or n == 3:
			print(1, 1)
		continue
	lol(n)


from math import floor
import sys
sys.setrecursionlimit(15000)

def Inverse(base, n, M):
	if n == 0:
		return 1
	if n == 1:
		return base
	half = Inverse(base, n // 2, M)
	if n % 2 == 0:
		return half ** 2 % M
	else:
		return half ** 2 % M * base % M

def inverse_arith(n, M):
	return Inverse(n, M - 2, M)
MOD = 1000000007
MOD1 = 1000000009
b1 = int(input())
for r in range(b1):
	h = int(input()) - 1
	i = h * (h + 1) // 2
	w = 2 * h - 1
	y2 = inverse_arith(w, MOD)
	z = i * y2 % MOD
	y3 = inverse_arith(w, MOD1)
	z1 = i * y3 % MOD1
	print(z, end=' ')
	print(z1)


from fractions import gcd

def binpow(a, b, m):
	r = 1
	while b:
		if b % 2:
			r = r * a % m
		b = b // 2
		a = a * a % m
	return r
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 9
t = int(input())
for _ in range(t):
	n = int(input()) - 1
	p = (n + 1) * n
	q = 2 * (2 * n - 1)
	g = gcd(p, q)
	(p, q) = (p // g, q // g)
	ans1 = p * binpow(q, mod1 - 2, mod1) % mod1
	ans2 = p * binpow(q, mod2 - 2, mod2) % mod2
	print(ans1, ans2)


def fastpow(a, n, m):
	if n == 0:
		return 1
	if n == 1:
		return a
	b = fastpow(a, n // 2, m)
	if n % 2 == 0:
		return b * b % m
	else:
		return b * b % m * a % m
t = int(input())
for i in range(0, t):
	n = int(input()) - 1
	num1 = fastpow(2 * (2 * n - 1), 1000000007 - 2, 1000000007)
	num2 = num1 * (n + 1) * n % 1000000007
	num3 = fastpow(2 * (2 * n - 1), 1000000009 - 2, 1000000009)
	num4 = num3 * (n + 1) * n % 1000000009
	print(str(num2) + ' ' + str(num4))


from fractions import gcd

def fermat(a, p, m):
	ans = 1
	a = a % m
	while p > 0:
		if p % 2 == 0:
			a = a * a % m
			p = p // 2
		else:
			ans = ans * a % m
			p -= 1
	return ans

def mod_inv(a, m):
	return fermat(a, m - 2, m)
T = int(input())
for r in range(T):
	n = int(input())
	n -= 1
	if n == 0:
		print(0, 0)
	else:
		num = (n + 1) * n * n
		den = 2 * n * (2 * n - 1)
		(m1, m2) = (10 ** 9 + 7, 10 ** 9 + 9)
		g = gcd(num, den)
		(num1, den1, num2, den2) = (num // g % m1, den // g % m1, num // g % m2, den // g % m2)
		(den1, den2) = (mod_inv(den1, m1), mod_inv(den2, m2))
		print(num1 * den1 % m1, num2 * den2 % m2)


def modinverse(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(int(input())):
	MOD1 = 1000000007
	MOD2 = 1000000009
	n = int(input())
	n -= 1
	if n == 0:
		print('0 0')
		continue
	p = n * (n + 1)
	q = 2 * (2 * n - 1)
	g = gcd(p, q)
	p //= g
	q //= g
	Q_1 = modinverse(q, MOD1)
	Q_2 = modinverse(q, MOD2)
	Q_1 = p % MOD1 * (Q_1 % MOD1) % MOD1
	Q_2 = p % MOD2 * (Q_2 % MOD2) % MOD2
	print(Q_1, end=' ')
	print(Q_2)


def gcd(a, b):
	if a % b is 0:
		return b
	else:
		return gcd(b, a % b)

def power(a, b, m):
	if b is 0:
		return 1
	k = power(a, b // 2, m)
	k = k % m * k % m
	if b % 2 is 1:
		return k % m * a % m % m
	else:
		return k % m

def inv(a, b):
	return power(a, b - 2, b)
for _ in range(0, int(input())):
	n = int(input())
	n = n - 1
	if n is 0:
		print('0 0')
	else:
		p = n * (n + 1)
		q = 2 * (2 * n - 1)
		g = gcd(p, q)
		p = p // g
		q = q // g
		mod1 = 1000000007
		mod2 = 1000000009
		q1 = inv(q, mod1)
		q2 = inv(q, mod2)
		a1 = p % mod1 * q1 % mod1 % mod1
		a2 = p % mod2 * q2 % mod2 % mod2
		s = str(a1) + ' ' + str(a2)
		print(s)


def power(a, b, m):
	if b is 0:
		return 1
	k = power(a, b // 2, m)
	k = k % m * k % m
	if b % 2 is 1:
		return k % m * a % m % m
	else:
		return k % m

def inv(a, b):
	return power(a, b - 2, b)

def gcd(a, b):
	if a % b is 0:
		return b
	else:
		return gcd(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	n = n - 1
	if n is 0:
		print('0 0')
	else:
		a = n * (n + 1)
		b = 2 * (2 * n - 1)
		g = gcd(a, b)
		a = a // g
		b = b // g
		mod = 10 ** 9 + 7
		mm = 10 ** 9 + 9
		b1 = inv(b, mod)
		b2 = inv(b, mm)
		a1 = a % mod * b1 % mod % mod
		a2 = a % mm * b2 % mm % mm
		print(str(a1) + ' ' + str(a2))


from fractions import gcd

def modInverse(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1
t = int(input())
for i in range(t):
	n = int(input())
	num = n * (n - 1)
	den = (2 * n - 3) * 2
	z = gcd(num, den)
	if z != 1:
		num = num // z
		den = den // z
	mod1 = 10 ** 9 + 7
	mod2 = 10 ** 9 + 9
	print(str(int(num % mod1 * modInverse(den, mod1) % mod1)) + ' ' + str(int(num % mod2 * modInverse(den, mod2) % mod2)))


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())
for i in range(t):
	n = int(input())
	n -= 1
	if n == 0:
		print(0, 0)
		continue
	ans1 = n * (n + 1) * modinv(2 * (2 * n - 1), 1000000007) % 1000000007
	ans2 = n * (n + 1) * modinv(2 * (2 * n - 1), 1000000009) % 1000000009
	print(ans1, ans2)


P1 = 1000000007
P2 = 1000000009
t = int(input())
for test in range(t):
	n = int(input()) - 1
	a = pow(n, 2) + n
	b = 4 * n - 2
	print(a % P1 * pow(b, P1 - 2, P1) % P1, a % P2 * pow(b, P2 - 2, P2) % P2)


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def inverse(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		n = n - 1
		if n == 0:
			print('0 0')
		else:
			num = (n + 1) * n
			den = 2 * (2 * n - 1)
			gc = gcd(num, den)
			num = num // gc
			den = den // gc
			m1 = 1000000007
			m2 = 1000000009
			ans1 = num * inverse(den, m1) % m1
			ans2 = num * inverse(den, m2) % m2
			print(str(ans1) + ' ' + str(ans2))
main()


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for u in range(t):
	n = int(input())
	num = n * (n - 1)
	den = 4 * n - 6
	g = gcd(num, den)
	num = num // g
	den = den // g
	print(num * pow(den, 1000000005, 1000000007) % 1000000007, num * pow(den, 1000000007, 1000000009) % 1000000009)


MOD1 = 10 ** 9 + 7
MOD2 = 10 ** 9 + 9

def power(acc, n, MOD):
	if n == 0:
		return 1
	if n % 2 == 1:
		return acc * power(acc * acc % MOD, int(n / 2), MOD)
	else:
		return power(acc * acc % MOD, int(n / 2), MOD)

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def solve(n):
	if n == 1:
		print(0, 0)
		return
	n -= 1
	numerator = n * n * (n + 1)
	denumerator = 2 * n * (2 * n - 1)
	g = gcd(numerator, denumerator)
	numerator //= g
	denumerator //= g
	print(numerator * power(denumerator, MOD1 - 2, MOD1) % MOD1, numerator * power(denumerator, MOD2 - 2, MOD2) % MOD2)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		solve(n)
main()


from fractions import gcd
t = int(input())

def binary_exp(x, n, prime):
	if n == 0:
		return 1
	elif n == 1:
		return x % prime
	else:
		temp = binary_exp(x, int(n / 2), prime)
		temp = temp * temp % prime
		if n % 2 == 0:
			return temp
		else:
			return x % prime * temp % prime

def inverse(x, prime):
	return binary_exp(x, prime - 2, prime)
while t != 0:
	t -= 1
	n = int(input())
	n = n - 1
	if n != 0:
		numerator = n * (n + 1)
		denominator = 2 * (2 * n - 1)
		factor = gcd(numerator, denominator)
		numerator = numerator // factor
		denominator = denominator // factor
		prime1 = 1000000007
		prime2 = 1000000009
		ans1 = numerator * inverse(denominator, prime1)
		ans2 = numerator * inverse(denominator, prime2)
		print(ans1 % prime1, ans2 % prime2)
	else:
		print('0 0')


cnt_tests = int(input())

def solve(n, MOD):
	p = n * (n + 1) % MOD
	q = (4 * n - 2) % MOD
	q_rev = pow(q, MOD - 2, MOD)
	return p * q_rev % MOD
for test in range(cnt_tests):
	n = int(input())
	print(solve(n - 1, int(1000000000.0) + 7), solve(n - 1, int(1000000000.0 + 9)))


MOD1 = 1000000007
MOD2 = 1000000009

def modpow(x, y, mod):
	if y == 0:
		return 1
	else:
		tmp = modpow(x, y // 2, mod)
		return tmp * tmp % mod if y % 2 == 0 else tmp * tmp % mod * x % mod
T = int(input())
for _ in range(T):
	N = int(input())
	if N == 1:
		print(0, 0)
	else:
		if N % 3 == 0:
			P = N // 3 * (N - 1) // 2
			Q = 2 * N // 3 - 1
		else:
			P = N * (N - 1) // 2
			Q = 2 * N - 3
		print(P * modpow(Q, MOD1 - 2, MOD1) % MOD1, P * modpow(Q, MOD2 - 2, MOD2) % MOD2)


def findmmi(n, m):
	return pow(n, m - 2, m)

def main():
	mod1 = 1000000007
	mod2 = 1000000009
	T = int(input())
	while T > 0:
		n = int(input())
		n = n - 1
		if n == 0:
			print('0 0')
		else:
			n1 = n % mod1 * (n + 1) % mod1 % mod1
			d1 = findmmi(4 * n - 2, mod1)
			ans1 = n1 % mod1 * (d1 % mod1) % mod1
			n2 = n % mod2 * (n + 1) % mod2 % mod2
			d2 = findmmi(4 * n - 2, mod2)
			ans2 = n2 % mod2 * (d2 % mod2) % mod2
			print(str(ans1) + ' ' + str(ans2))
		T = T - 1
main()


def ModInverse(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 = x1 + m0
	return x1
T = int(input())
for i in range(T):
	Num = int(input())
	if Num > 1:
		P = Num * (Num - 1)
		Q = 2 * (2 * Num - 3)
		Q1 = ModInverse(Q, 10 ** 9 + 7)
		Q2 = ModInverse(Q, 10 ** 9 + 9)
		Ans1 = P * Q1 % (10 ** 9 + 7)
		Ans2 = P * Q2 % (10 ** 9 + 9)
		print(Ans1, Ans2)
	else:
		print(0, 0)


from fractions import gcd
get = lambda p, q, m: p * pow(q, m - 2, m) % m
for t in range(int(input())):
	N = int(input())
	(num, den) = (N * (N - 1), 4 * N - 6)
	g = gcd(num, den)
	num //= g
	den //= g
	ans1 = get(num, den, 10 ** 9 + 7)
	ans2 = get(num, den, 10 ** 9 + 9)
	print(ans1, ans2)


t = int(input())

def modexp(x, y, p):
	res = 1
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(0, t):
	mod1 = 1000000005
	mod2 = 1000000007
	mod3 = 1000000009
	n = int(input())
	if n == 1:
		print(0, 0)
	else:
		a = int(n * (n - 1) // 2)
		b = 2 * n - 3
		x = int(a // gcd(a, b))
		y = int(b // gcd(a, b))
		xx = modexp(y, mod1, mod2)
		xy = x % mod2
		x1 = xy * xx % mod2
		yx = modexp(y, mod2, mod3)
		yy = x % mod3
		x2 = yy * yx % mod3
		print(x1, x2)


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def fast_pow(x, y, M):
	if y == 0:
		return 1
	p = fast_pow(x, y // 2, M)
	p = p * p % M
	if y % 2 == 0:
		return p
	else:
		return p * x % M

def modInverse(x, M):
	return fast_pow(x, M - 2, M)
for _ in range(int(input())):
	n = int(input())
	if n < 2:
		print('0 0')
		continue
	(nu, de) = ((n - 1) * (n - 1) * n, (2 * n - 2) * (2 * n - 3))
	d = gcd(nu, de)
	(nu, de) = (nu // d, de // d)
	(ans1, ans2) = (nu * modInverse(de, 10 ** 9 + 7) % (10 ** 9 + 7), nu * modInverse(de, 10 ** 9 + 9) % (10 ** 9 + 9))
	print(ans1, ans2)


import functools, operator
cases = int(input())
mod1 = 1000000007
mod2 = 1000000009

def ncr(n, r):
	r = min(r, n - r)
	if r == 0:
		return 1
	return functools.reduce(operator.mul, range(n, n - r, -1)) // functools.reduce(operator.mul, range(1, r + 1))

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)
	return x % m
for _ in range(cases):
	n = int(input())
	if n == 1:
		print(0, 0)
	elif n == 2 or n == 3:
		print(1, 1)
	else:
		p = (n - 1) * n
		q = (2 * n - 3) * 2
		qmod1 = modinv(q, mod1)
		qmod2 = modinv(q, mod2)
		print(p * qmod1 % mod1, p * qmod2 % mod2)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
T = int(input())
for i in range(T):
	n = int(input())
	numerator = n * (n - 1)
	denominator = 2 * (2 * n - 3)
	a = gcd(numerator, denominator)
	numerator = numerator // a
	denominator = denominator // a
	ans = pow(denominator, 1000000005, 1000000007)
	ans = ans * numerator % 1000000007
	ans1 = pow(denominator, 1000000007, 1000000009)
	ans1 = ans1 * numerator % 1000000009
	print(ans, ans1)


from fractions import gcd
t = int(input())
for i in range(t):
	x = int(input())
	if x == 1:
		print(0, 0)
		continue
	p = (x - 1) * x
	q = (2 * x - 3) * 2
	k = gcd(p, q)
	p = p // k
	q = q // k
	yo = 10 ** 9 + 7
	y = pow(q, yo - 2, yo)
	an = y * p % yo
	yo = 10 ** 9 + 9
	y = pow(q, yo - 2, yo)
	an2 = y * p % yo
	print(an, an2)


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

def binpow(a, y, mod):
	res = 1
	a = a % mod
	while y > 0:
		if y % 2 == 1:
			res = res * a % mod
		y = y // 2
		a = a * a % mod
	return res
mod7 = 1000000007
mod9 = 1000000009

def inv7(a):
	return binpow(a, mod7 - 2, mod7)

def inv9(a):
	return binpow(a, mod9 - 2, mod9)
T = int(input())
for _ in range(0, T):
	n = int(input())
	if n == 1:
		print(0, 0)
	else:
		d = gcd(n * (n - 1), 4 * n - 6)
		P = n * (n - 1) // d
		Q = (4 * n - 6) // d
		print(P * inv7(Q) % mod7, P * inv9(Q) % mod9)


def inv(n, m):
	(nn, nm, mn, mm) = (1, 0, 0, 1)
	while m:
		(div, mod) = divmod(n, m)
		nn -= mn * div
		nm -= mm * div
		n = mod
		(n, m) = (m, n)
		(nn, nm, mn, mm) = (mn, mm, nn, nm)
	return nn
P7 = 10 ** 9 + 7
P9 = 10 ** 9 + 9

def ans(n, p):
	n %= p
	ans = (n - 1) * (n - 1) * n % p
	ans = ans * inv((2 * n - 2) % p, p) % p
	ans = ans * inv((2 * n - 3) % p, p) % p
	return ans
T = int(input())
for _ in range(T):
	N = int(input())
	if N == 1:
		print('0 0')
	else:
		print('{} {}'.format(ans(N, P7), ans(N, P9)))


from fractions import gcd
for t in range(int(input())):
	n = int(input())
	b = n - 1
	num = b * (b + 1)
	den = 4 * b - 2
	g = gcd(num, den)
	num = num // g
	den = den // g
	p = 1000000007
	y1 = num * pow(den, p - 2, p) % p
	y2 = num * pow(den, p, p + 2) % (p + 2)
	if n == 0 or n == 1:
		print('0 0')
	else:
		print(y1, y2)


def modInverse(a, m):
	m0 = m
	x0 = 0
	x1 = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += m0
	return x1

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for i in range(int(input())):
	n = int(input())
	p = n * (n - 1) * (n - 1)
	q = (2 * n - 2) * (2 * n - 3)
	m1 = 10 ** 9 + 7
	m2 = 10 ** 9 + 9
	if p == 0 or q == 0:
		print('0', '0')
		continue
	if p == q:
		print('1', '1')
		continue
	g = gcd(p, q)
	p = p // g
	q = q // g
	print(p * modInverse(q, m1) % m1, p * modInverse(q, m2) % m2)


MOD1 = 1000000007
MOD2 = 1000000009

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

def modexp(a, b, c):
	MOD = 3
	if c == 1:
		MOD = MOD1
	else:
		MOD = MOD2
	a = int(a % MOD)
	fin = int(1)
	ct = 0
	while b > 0:
		if b % 2 == 1:
			fin = fin * a % MOD
		a = a * a % MOD
		b = int(b / 2)
	return fin

def inverse(a, b):
	if b == 1:
		return int(modexp(a, MOD1 - 2, 1))
	else:
		return int(modexp(a, MOD2 - 2, 2))
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	if n == 1:
		print('0 0')
		continue
	a = int(n * (n - 1))
	b = int(2 * (2 * n - 3))
	gf = int(gcd(a, b))
	print(int(a * inverse(b, 1)) % MOD1, end=' ')
	print(int(a * inverse(b, 2)) % MOD2)