Given a sequence A of length N, the weight of this sequence is defined as

\text{weight}(A) = \sum_{i = 1}^{N} i\cdot A_{i}

Given an integer N, we pick a permutation A of [1, 2 \dots N] uniformly at random. What is the expected weight of this permutation?

It can be shown that the answer can be represented as \displaystyle \frac{P}{Q} where P and Q are coprime integers and Q \neq 0 \pmod{998244353}. Print the value of P \cdot Q^{-1} modulo 998244353.

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

- First line of the input contains T, the number of test cases. Then the test cases follow.
- Each test case contains a single integer on a single line N.

------ Output Format ------ 

For each test case, print a single integer, the answer to the test case.

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

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

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

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

----- Sample Output 1 ------ 
1
499122181
12

----- explanation 1 ------ 
- Test case $1$: There is only one permutation of $[1]$ which is $[1]$ and the weight of this permutation is equal to $1$. So, the expected weight is equal to $1$.
- Test case $2$: There are $2$ permutations of $[1, 2]$ namely
- $[1, 2]$ with weight equal to $5$.
- $[2, 1]$ with weight equal to $4$.

So, the expected weight is equal to $\frac{5 + 4}{2!} = \frac{9}{2}$.
- Test case $3:$
There are $6$ permutations of $[1, 2, 3]$ namely
- $[1, 2, 3]$ with weight equal to $14$.
- $[1, 3, 2]$ with weight equal to $13$.
- $[2, 1, 3]$ with weight equal to $13$.
- $[2, 3, 1]$ with weight equal to $11$.
- $[3, 1, 2]$ with weight equal to $11$.
- $[3, 2, 1]$ with weight equal to $10$.

So, the expected weight is equal to $\frac{14 + 13 + 13 + 11 + 11 + 10}{3!} = 12$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Probability

Starter code:

Solutions:
mod = 998244353
for _ in range(int(input())):
	N = int(input())
	p = int((N + N % 2) // 2 * (N + int(not bool(N % 2))))
	if N % 2 == 1:
		if p % 2 == 0:
			p = p // 2 * (N + 1) % mod
		else:
			p = (N + 1) // 2 * p % mod
	else:
		p = p * (N + 1) % mod
		x = pow(2, -1, mod)
		p = p * x % mod
	print(int(p % mod))


t = int(input())
for _ in range(t):
	n = int(input())
	if n * (n + 1) * (n + 1) % 4 == 0:
		print(n * (n + 1) * (n + 1) // 4 % 998244353)
	else:
		x = n * (n + 1) * (n + 1)
		x = x // 2
		print(x * 499122177 % 998244353)


t = int(input())
for _ in range(t):
	n = int(input())
	mod = 998244353
	a = 1
	b = 0
	if n % 2 == 0:
		if n % 4 == 0:
			b = 1
			a = n // 4
			a %= mod
			a *= n + 1
			a %= mod
			a *= n + 1
			a %= mod
		else:
			b = 2
			a = n // 2
			a %= mod
			a *= n + 1
			a %= mod
			a *= n + 1
			a %= mod
	else:
		b = 1
		a *= (n + 1) // 2
		a %= mod
		a *= (n + 1) // 2
		a %= mod
		a *= n
		a %= mod
	inv = 0
	if b == 1:
		inv = 1
	elif b == 2:
		inv = 499122177
	ans = a * inv
	ans %= mod
	print(int(ans))


mod = 998244353
t = int(input())
for i in range(t):
	n = int(input())
	c = (n + 1) ** 2 * n
	d = 4
	c %= mod
	if not c & 3:
		c >>= 2
		d = 1
	elif not c & 1:
		c >>= 1
		d = 2
	print(c * pow(d, mod - 2, mod) % mod)


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
modd = 998244353
t = int(input())
for hh in range(0, t):
	n = int(input())
	if n % 2 == 0:
		ans1 = n // 2 * (n + 1) % modd
	else:
		ans1 = (n + 1) // 2 * n % modd
	if ans1 % 2 == 0 or (n + 1) % 2 == 0:
		if ans1 % 2 == 0:
			ans = ans1 // 2 * (n + 1) % modd
		else:
			ans = (n + 1) // 2 * ans1 % modd
		print(ans)
	else:
		qinv = modInverse(2, modd)
		ans = ans1 * (n + 1) % modd
		ans = ans * qinv % modd
		print(ans)


mod = 998244353
n = int(input())
for i in range(n):
	num = int(input())
	numerator = (num + 1) ** 2 * num
	denominator = 4
	numerator %= mod
	if not numerator & 3:
		numerator >>= 2
		denominator = 1
	elif not numerator & 1:
		numerator >>= 1
		denominator = 2
	print(numerator * pow(denominator, mod - 2, mod) % mod)


from math import gcd

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

def reduceFrac(p, q):
	d = gcd(p, q)
	p = p // d
	q = q // d
	print(calculate(p, q))
for _ in range(int(input())):
	n = int(input())
	p = n * n * (n + 1) * (n + 1) // 4
	q = n
	reduceFrac(p, q)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	if n * (n + 1) * (n + 1) % 4 == 0:
		ans.append(n * (n + 1) * (n + 1) // 4 % 998244353)
	else:
		x = n * (n + 1) * (n + 1)
		x = x // 2
		ans.append(x * 499122177 % 998244353)
for i in ans:
	print(i)


import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
for i in range(n):
	num = int(input())
	numerator = (num + 1) ** 2 * num
	denominator = 4
	numerator %= mod
	if not numerator & 3:
		numerator >>= 2
		denominator = 1
	elif not numerator & 1:
		numerator >>= 1
		denominator = 2
	print(numerator * pow(denominator, mod - 2, mod) % mod)


mod = 998244353

def power(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	ret = power(a, b // 2)
	if b % 2 == 0:
		return ret * ret % mod
	else:
		return ret * ret % mod * a % mod
t = int(input())
for i in range(t):
	n = int(input())
	ans = n * (n + 1) % mod * (n + 1) % mod
	ans = ans * power(4, mod - 2) % mod
	print(ans)


for a0 in range(int(input())):
	n = int(input())
	if n * (n + 1) * (n + 1) % 4 == 0:
		print(n * (n + 1) * (n + 1) // 4 % 998244353)
	else:
		x = n * (n + 1) * (n + 1)
		x = x // 2
		print(x * 499122177 % 998244353)


t = int(input())
while t > 0:
	mod = 998244353
	n = int(input())

	def gcd(a, b):
		if b == 0:
			return a
		return gcd(b, a % b)
	res = n * (n + 1) * (n + 1)
	h = gcd(res, 4)
	a = res // h
	b = 4 // h

	def modexp(x, n):
		if n == 0:
			return 1
		elif n % 2 == 0:
			return modexp(x * x % mod, n // 2)
		else:
			return x * modexp(x * x % mod, (n - 1) / 2) % mod
	d = modexp(b, mod - 2)
	sol = a % mod * (d % mod) % mod
	print(sol)
	t = t - 1


from math import ceil
MOD = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	k = n + 1
	val = n * k * k
	ans = 0
	if val % 4 == 0:
		ans = val // 4
	else:
		ans = val // 2
		ans = ans * ceil(MOD / 2)
	print(ans % MOD)


import sys
import math
from math import gcd, sqrt
import heapq as hq
from bisect import bisect_right, bisect_left, bisect
import itertools
from sys import stdin, stdout, setrecursionlimit

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
T = 1
T = int(stdin.readline())
MOD = int(1000000000.0) + 7
for _ in range(T):
	n = int(stdin.readline())
	P = n * (n + 1) * (n + 1)
	Q = 4
	print(calculate(P, Q))


mod = 998244353

def power(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	ret = power(a, b // 2)
	if b % 2 == 0:
		return ret * ret % mod
	else:
		return ret * ret % mod * a % mod
try:
	t = int(input())
	while t > 0:
		n = int(input())
		ans = n * (n + 1) % mod * (n + 1) % mod
		ans = ans * power(4, mod - 2) % mod
		print(ans)
		t = t - 1
except:
	pass


m = 998244353
v = 499122177
T = int(input())
for i in range(T):
	N = int(input())
	if N & 1 == 1:
		next = (N + 1) % m
		half = next * v % m
		res = half * half % m
		res = res * N % m
	else:
		next = (N + 1) % m
		half = N * v % m
		res = next * next % m
		res = res * half % m
		res = res * v % m
	print(int(res))


def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
for _ in range(int(input())):
	n = int(input())
	val = n * (n + 1) * (n + 1)
	print(calculate(val, 4))


mod = 998244353
div = pow(4, mod - 2, mod)

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


T = int(input())
for tc in range(T):
	n = int(input())
	w = n * (n + 1) ** 2
	if w // 4 == 0:
		print(w // 4)
	else:
		print(w // 2 * 499122177 % 998244353)


t = int(input())
a = []
for i in range(0, t):
	a += [list(map(int, input().split()))]

def f(n):
	l = n * (n + 1) ** 2
	if l % 4 == 0:
		return l // 4 % 998244353
	elif l % 2 == 0:
		return l // 2 * 499122177 % 998244353
	else:
		return l * 748683265 % 998244353
for i in range(0, t):
	print(f(a[i][0]))


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	mod = 998244353
	ans = n * (n + 1) % mod * (n + 1) % mod
	ans = ans * pow(4, mod - 2, mod) % mod
	print(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 Q1(S, A, B, C):
	p = S * (1 + C / 100)
	return 'YES' if p >= A and p <= B else 'NO'

def Q2(N, K):

	def hcf(x, y):
		return hcf(y, x % y) if y else x
	return N // hcf(N, K)

def Q3(N):
	return N * pow(N + 1, 2, MOD) * Q_inv % MOD
MOD = 998244353
Q_inv = mod_inv(4)
for _ in range(inp()):
	N = inp()
	outp(Q3(N))


def gcdEx(p, q):
	if p == 0:
		return (q, 0, 1)
	(gcd, x1, y1) = gcdEx(q % p, p)
	x = y1 - q // p * x1
	y = x1
	return (gcd, x, y)

def gcd(a, b):
	if a >= b:
		c = b
		d = a
	else:
		(c, d) = (a, b)
	while not d % c == 0:
		a = d - c
		b = c
		if a >= b:
			c = b
			d = a
		else:
			(c, d) = (a, b)
	return c
t = int(input())
for i in range(t):
	n = int(input())
	s = n * (n + 1) ** 2
	if n % 2 == 0:
		(_, q, _) = gcdEx(2, 998244353)
		s = s // 2
		s *= q
		print(s % 998244353)
	else:
		s = s // 4
		print(s % 998244353)


t = int(input())
while t > 0:
	n = int(input())
	mod = 998244353
	ans = n * (n + 1) % mod * (n + 1) % mod
	print(ans * 748683265 % mod)
	t -= 1


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	ans = n * (n + 1) % mod * (n + 1) % mod
	temp = pow(4, mod - 2, mod)
	ans = ans * temp % mod
	print(ans)


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

def summation(x):
	ret = x * (x + 1) // 2
	return ret
for _ in range(int(input())):
	n = int(input())
	p = summation(n) ** 2
	q = n
	ans = calculate(p, q)
	print(ans)


m = 998244353
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		inv = (m + 1) // 2 % m
		pro = n // 2 * (n + 1) ** 2 % m
		print(pro * inv % m)
	else:
		pro = n * ((n + 1) // 2) ** 2 % m
		print(pro)


t = int(input())
m = 998244353
while t:
	n = int(input())
	if n % 2 == 0:
		inv = (m + 1) // 2 % m
		pro = n // 2 * (n + 1) * (n + 1) % m
		print(pro * inv % m)
	else:
		pro = n * ((n + 1) // 2) * ((n + 1) // 2) % m
		print(pro)
	t = t - 1


mod = 998244353

def power(p, q):
	if q == 0:
		return 0
	elif q == 1:
		return p
	else:
		res = power(p, q // 2)
		if q & 1:
			return res * res % mod * p % mod
		else:
			return res * res % mod
T = int(input())
for i in range(T):
	n = int(input())
	P = n ** 3 + 2 * (n * n) + n
	P = P * power(4, mod - 2) % mod
	print(P)


def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
for _ in range(int(input())):
	n = int(input())
	numerator = n * (n + 1) * (n + 1)
	deno = 4
	modinv = calculate(numerator, deno)
	print(modinv)


from sys import stdin
inp = stdin.readline
mod = 998244353
T = int(inp())
ans = []
for tx in range(T):
	N = int(inp())
	Tn = N * (N + 1) // 2
	if N % 4 == 2:
		P = Tn * Tn * 2 // N % mod
		if P % 2 == 0:
			ans.append(P // 2)
		else:
			ans.append((P + mod) // 2)
	else:
		ans.append(Tn * Tn // N % mod)
print(*ans, sep='\n')


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

def solver(n):
	m = 998244353
	num = n % m * (n + 1) % m * (n + 1) % m * fastPower(4, m - 2) % m
	return num
t = int(input())
for i in range(t):
	n = int(input())
	print(solver(n))


def f(n):
	l = n * (n + 1) ** 2
	if l % 4 == 0:
		return l // 4 % 998244353
	elif l % 2 == 0:
		return l // 2 * 499122177 % 998244353
	else:
		return l * 748683265 % 998244353
t = int(input())
for _ in range(t):
	print(f(int(input())))


def sol(N):
	ans = N * ((N + 1) * (N + 1)) * 748683265 % 998244353
	return ans
t = int(input())
while t > 0:
	N = int(input())
	print(sol(N))
	t = t - 1


def fun(p, q):
	mod = 998244353
	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 * (n + 1) // 2
	res = fun(p ** 2, n)
	print(res)


for _ in range(int(input())):
	n = int(input())
	p = n * (n + 1) * (n + 1)
	q = 4
	mod = 998244353
	tem = mod - 2
	while tem:
		if tem & 1:
			p = p * q % mod
		q = q * q % mod
		tem >>= 1
	print(p)


mod = 998244353

def modInv(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
for _ in range(int(input())):
	n = int(input())
	x = modInv(4, mod)
	sump = n * (n + 1) ** 2
	ans = sump % mod * (x % mod) % mod
	print(ans)


try:

	def calculate(p, q):
		mod = 998244353
		expo = 0
		expo = mod - 2
		while expo:
			if expo & 1:
				p = p * q % mod
			q = q * q % mod
			expo >>= 1
		return p
	for t in range(int(input())):
		N = int(input())
		temp1 = (N + 1) * (N + 1) % 998244353
		temp2 = N * temp1 % 998244353
		print(calculate(temp2, 4))
except:
	pass


mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 4 == 0 or (n + 1) * (n + 1) % 4 == 0:
		ans = n * (n + 1) ** 2 // 4
		ans = ans % mod
		print(ans)
	else:
		ans = n * (n + 1) ** 2 % mod
		ans *= pow(4, mod - 2, mod)
		ans = ans % mod
		print(ans)


t = int(input())
while t > 0:
	n = int(input())
	if n % 4 == 0:
		p = 1
		p *= n + 1
		p %= 998244353
		p *= n + 1
		p %= 998244353
		p *= n // 4
		p %= 998244353
		print(p)
	elif n % 2 == 0:
		p = 1
		p *= n + 1
		p %= 998244353
		p *= n + 1
		p %= 998244353
		p *= n // 2
		p %= 998244353
		print(p * 499122177 % 998244353)
	else:
		p = 1
		p *= n
		p %= 998244353
		p *= n // 2 + 1
		p %= 998244353
		p *= n // 2 + 1
		p %= 998244353
		print(p)
	t -= 1


def calculateMod(p, q):
	_mod = 998244353
	expo = _mod - 2
	while expo:
		if expo & 1:
			p = p * q % _mod
		q = q * q % _mod
		expo >>= 1
	return p

def _func(n):
	p = n * pow(n + 1, 2) // 2
	if n & 1:
		return calculateMod(p // 2, 1)
	else:
		return calculateMod(p, 2)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(_func(n))
main()


import math

def calculate(p, q):
	mod = 998244353
	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:
	n = int(input())
	k = n * (n + 1) // 2 * (n * (n + 1) // 2)
	print(calculate(k, n))
	t -= 1


from fractions import Fraction
t = int(input())
m = 998244353
for i in range(t):
	n = int(input())
	sn = n * (n + 1) // 2
	sm = sn * sn
	ans = Fraction(sm, n)
	nmr = ans.numerator % m
	if ans.denominator == 1:
		print(nmr)
	else:
		print(nmr * 499122177 % m)


import math

def calculate(a, b):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			a = a * b % mod
		b = b * b % mod
		expo >>= 1
	return a
t = int(input())
while t:
	t -= 1
	n = int(input())
	print(calculate(n * (n + 1) * (n + 1), 4))


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for i in range(0, t):
	n = int(input())
	S = n * (n + 1) // 2
	ans = S * S
	ans = ans
	if ans % n == 0:
		print(ans // n % 998244353)
	else:
		A = ans // n
		B = ans % n
		p = A * n + B
		q = n
		P = p // gcd(p, q)
		Q = q // gcd(p, q)
		L = 998244353 // Q + 1
		M = (998244353 // Q + 1) * Q - 998244353
		P = P // M
		print(P * L % 998244353)


import sys
L = sys.stdin.readlines()
T = int(L[0])
M = 998244353

def mod_exp(x, n, m):
	if n == 0:
		return 1
	return (1 + n % 2 * (x - 1)) * mod_exp(x, n >> 1, m) ** 2 % m

def exp_weight(N):
	P = N * (N + 1) ** 2
	return P % M * (mod_exp(4, M - 2, M) % M) % M
for t in range(T):
	N = int(L[1 + t])
	print(exp_weight(N))


def calculate(p, q):
	mod = 998244353
	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 z in range(t):
	n = int(input())
	p = n * (n + 1) * (n + 1)
	if p % 4 == 0:
		p = p // 4
		q = 1
	elif p % 2 == 0:
		p = p // 2
		q = 2
	else:
		q = 4
	print(calculate(p, q))


from math import gcd

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return -1
	else:
		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

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
m = 998244353
r = modInverse(4, m)
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	l = n % m * ((n + 1) % m) * ((n + 1) % m) * (r % m) % m
	print(l)


mod = 998244353

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

def modexp(x, n):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return modexp(x * x % mod, n // 2)
	else:
		return x * modexp(x * x % mod, (n - 1) / 2) % mod

def getFractionModulo(a, b):
	c = gcd(a, b)
	a = a // c
	b = b // c
	d = modexp(b, mod - 2)
	ans = a % mod * (d % mod) % mod
	return ans
for _ in range(int(input())):
	n = int(input())
	c = (n + 1) * (n * (n + 1) // 2)
	if c % 2 == 0:
		c //= 2
		print(c % mod)
	else:
		print(getFractionModulo(c, 2))