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

Chef recently read about the mex function and came up with a function similar to that. For a (possibly empty) sequence of positive integers $S$, Chef defines $f(S)$ as the smallest positive integer that does not appear in $S$. For example, $f([])=1$, $f([3,4,3,5])=1$, $f([2,5,1,1,2,3])=4$.

Chef's friend heard about Chef's idea and found it really cool. Therefore, he sent a sequence $a_{1}, a_{2}, \ldots, a_{N}$ to Chef and asked him to find the sum of $f(S)$ over all $2^{N}$ possible subsequences $S$ of this sequence. Since Chef is busy, he entrusted you with solving the problem.

Since the resulting sum can be very big, compute it modulo $998,244,353$.

------  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 line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the sum of $f(S)$ over all subsequences modulo $998,244,353$.

------  Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N ≤ 10^{5}$
$1 ≤ a_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (50 points): the sum of $N$ over all test cases does not exceed $1,000$

Subtask #2 (50 points): original constraints

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

2

1 1

3

1 2 1
----- Sample Output 1 ------ 
7

17
----- explanation 1 ------ 
Example case 1: The values for all possible subsequences are $f([])=1$, $f([1])=2$, $f([1])=2$, $f([1,1])=2$.

Example case 2: The values for all possible subsequences are $f([])=1$, $f([1])=2$, $f([2])=1$, $f([1])=2$, $f([1,2])=3$, $f([2,1])=3$, $f([1,1])=2$, $f([1,2,1])=3$.

Source: codechef | Difficulty: HARD
Tags: Number theory

Mathematics


Solutions:
import sys
from collections import defaultdict, deque
import math
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = inp()
	freq = defaultdict(int)
	for i in a:
		if i not in freq:
			freq[i] = 1
		else:
			freq[i] += 1
	mul = 1
	add = 0
	res = 0
	for i in range(1, n + 1):
		mex = i * mul % mod
		add = (add + freq[i]) % mod
		mex = mex * pow(2, n - add, mod) % mod
		res = (res + mex) % mod
		mul = mul * (pow(2, freq[i], mod) - 1) % mod
	print(res)


import sys
input = sys.stdin.readline
M = 998244353
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().rstrip().split(' ')))
	freq = [0 for __ in range(N + 1)]
	left = [0 for __ in range(N + 1)]
	right = [0 for __ in range(N + 1)]
	s = 0
	extra = 0
	for a in A:
		if a > N:
			extra += 1
		else:
			freq[a] += 1
	left[0] = 1
	right[0] = (1 << extra) % M
	right[N] = (1 << freq[N]) * right[0] % M
	for i in range(1, N + 1):
		left[i] = ((1 << freq[i]) - 1) * left[i - 1] % M
	for i in range(N - 1, 0, -1):
		right[i] = (1 << freq[i]) * right[i + 1] % M
	for i in range(1, N):
		s += i * (left[i - 1] * right[i + 1])
		s %= M
	s += N * (left[N - 1] * right[0])
	s += (N + 1) * left[N]
	print(s % M)


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
m = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().strip().split()))
	map1 = dict()
	for val in list1:
		if val in map1:
			map1[val] += 1
		else:
			map1[val] = 1
	list2 = sorted(map1)
	mex = len(list2) + 1
	for i in range(mex - 1):
		if list2[i] != i + 1:
			mex = i + 1
			break
	ans = 0
	done = 0
	mul = 1
	sub = 0
	for i in range(1, mex):
		count = map1[list2[i - 1]]
		done += count
		rem = n - done
		temp = power(2, rem, m) * mul
		temp = temp % m
		sub += temp
		ans += temp * i
		ans = ans % m
		mul = mul * (power(2, count, m) - 1)
		mul = mul % m
	ans += (power(2, n, m) - sub) * mex
	ans = ans % m
	print(ans)


import math, sys
from collections import Counter as cc
from collections import defaultdict as dd
from math import factorial as fact
sys.setrecursionlimit(10 ** 6)
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		if a[i] > n + 1:
			a[i] = n + 1
	c = dd(lambda : 0)
	for i in a:
		c[i] += 1
	count = [0] * (n + 2)
	for i in range(n, -1, -1):
		count[i] = (count[i + 1] + c[i + 1]) % mod
	d = [1] * (n + 10)
	d[1] = 2 ** c[1] - 1
	for i in range(2, n + 2):
		d[i] = d[i - 1] * (pow(2, c[i]) - 1) % mod
	ans = 0
	for i in range(1, n + 2):
		ans += i * pow(2, count[i], mod) * (d[i - 1] % mod) % mod
	print(ans % mod)


import sys
from collections import Counter

def fin():
	return sys.stdin.readline().strip()

def fout(s, sep='\n'):
	sys.stdout.write(str(s) + sep)
MOD = 998244353
test = int(input())
for _ in range(test):
	n = int(fin())
	a = [int(x) for x in fin().split()]
	count = Counter(a)
	missing = None
	for i in range(1, n + 2):
		if i not in count:
			missing = i
			break
	if 1 not in count:
		ans = 2 ** n % MOD
	else:
		prev = count[1]
		prev2 = pow(2, count[1], MOD) - 1
		ans = pow(2, n - count[1], MOD)
		for i in range(2, missing):
			ans = (ans + i * prev2 * pow(2, n - count[i] - prev, MOD) % MOD) % MOD
			prev += count[i]
			prev2 = prev2 * (pow(2, count[i], MOD) - 1) % MOD
		ans = (ans + prev2 * missing % MOD * pow(2, n - prev, MOD) % MOD) % MOD
	print(ans)


from collections import Counter
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	dct = Counter(ls)
	if dct[1] == 0:
		print(pow(2, n, mod))
	else:
		presm = [0 for i in range(n + 2)]
		presm[0] = n
		for i in range(1, n + 1):
			presm[i] = presm[i - 1] - dct[i]
		ans = pow(2, n - dct[1], mod)
		pro = pow(2, dct[1], mod) - 1
		for i in range(2, n + 2):
			ans = (ans + pro * pow(2, presm[i], mod) * i % mod) % mod
			pro = pro * (pow(2, dct[i], mod) - 1) % mod
		print(ans)


from collections import defaultdict

def zeroes():
	return 0
m = 998244353
k = pow(10, 5) + 5
powers = [1] * k
d = defaultdict(zeroes)
for i in range(1, k):
	powers[i] = 2 * powers[i - 1] % m
T = int(input())
while T > 0:
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		d[a[i]] += 1
	sum = 0
	prod = 1
	ans = 0
	mex = 0
	for i in range(1, n + 2):
		sum = (sum + d[i]) % m
		mex = prod * i % m
		mex = mex * powers[n - sum] % m
		ans = (ans + mex) % m
		prod = prod * (powers[d[i]] - 1) % m
		d[i] = 0
	print(ans)
	T -= 1


from collections import defaultdict
mod = 998244353
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	f = defaultdict(int)
	for j in lst:
		f[j] += 1
	ans = 0
	_mul = 1
	_sum = f[1]
	for m in range(2, n + 2):
		_mul = _mul * (pow(2, f[m - 1], mod) - 1) % mod
		_sum = _sum + f[m]
		gm = n - _sum
		ans = ans + m * pow(2, gm, mod) * _mul % mod
		ans = ans % mod
	ans = ans + pow(2, n - f[1], mod)
	ans = ans % mod
	print(int(ans))


from sys import stdin, stdout
power = [1]
mod = 998244353
for i in range(1, 100006):
	power.append(2 * power[i - 1] % mod)
from collections import Counter
for testcases in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	count = Counter(arr)
	remaining = 0
	res = 0
	prev = 1
	for mex in range(1, n + 2):
		remaining += count[mex]
		remaining %= mod
		res += mex * prev * power[n - remaining]
		res %= mod
		prev *= power[count[mex]] - 1
		prev %= mod
	print(res)


import numpy as np
mod = 998244353
two = [1]
for i in range(1, 10 ** 5 + 100):
	two.append(2 * two[i - 1] % mod)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	freq = [0] * (n + 5)
	for x in a:
		freq[min(x, n + 1)] += 1
	sf = [0] * (n + 5)
	for i in range(n + 3, -1, -1):
		sf[i] = sf[i + 1] + freq[i]
	ans = 0
	pf = 1
	for i in range(1, n + 1):
		ans = (ans + i * (pf * two[sf[i + 1]] % mod)) % mod
		pf = pf * (two[freq[i]] - 1) % mod
	ans %= mod
	print(ans)


T = int(input())
m = 998244353
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i1 in range(n):
		if a[i1] not in d:
			d[a[i1]] = 0
		d[a[i1]] += 1
	ans = 0
	mul = 1
	add = 0
	for i2 in range(len(d) + 1):
		if i2 < len(d):
			if i2 + 1 not in d:
				k = (i2 + 1) * mul * pow(2, n - add, m) % m
				ans += k
				break
			else:
				add += d[i2 + 1]
				k = (i2 + 1) * mul * pow(2, n - add, m) % m
				ans += k
				mul *= (pow(2, d[i2 + 1], m) - 1) % m
		else:
			ans += mul * (i2 + 1) % m
	print(ans % m)


mod = 998244353
pow2 = [1]
for i in range(10 ** 5 + 5):
	tmp = pow2[-1]
	tmp *= 2
	tmp %= mod
	pow2.append(tmp)
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	l = {}
	for i in A:
		if i in l:
			l[i] += 1
		else:
			l[i] = 1
	minn = 1
	ans = 0
	a = 1
	b = 0
	A = sorted(list(set(A)))
	for i in A:
		tmp = a
		b += l[i]
		tmp *= pow2[n - b]
		tmp *= minn
		tmp %= mod
		ans += tmp
		if i == minn:
			minn += 1
		a *= pow2[l[i]] - 1
		a %= mod
	ans += a * minn % mod
	ans %= mod
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	values = list(map(int, input().split()))
	occ = [0] * (n + 2)
	for i in values:
		if i <= n + 1:
			occ[i] += 1
	mod = 998244353
	ans = 0
	p1 = [0] * (n + 2)
	for i in range(1, n + 2):
		p1[i] = p1[i - 1] + occ[i]
	power_p1 = [1] * (n + 2)
	power_p2 = [1] * (n + 2)
	for i in range(1, n + 2):
		power_p1[i] = pow(2, n - p1[i], mod)
	for i in range(2, n + 2):
		power_p2[i] = power_p2[i - 1] * (pow(2, occ[i - 1], mod) - 1) % mod
	ans = 0
	for i in range(1, n + 2):
		ans = (ans + power_p1[i] * power_p2[i] % mod * i % mod) % mod
	print(ans)
	t -= 1


pow_2 = [1]
mod = 998244353
for i in range(1, 10 ** 5 + 1):
	pow_2.append(pow_2[-1] * 2 % mod)
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	fre = [0] * (10 ** 5 + 2)
	for i in range(n):
		if arr[i] > 10 ** 5:
			fre[10 ** 5] += 1
		else:
			fre[arr[i]] += 1
	com = [0]
	for i in range(1, 10 ** 5 + 2):
		com.append(com[-1] + fre[i])
	temp = [1]
	for i in range(1, 10 ** 5 + 1):
		if fre[i] == 0:
			break
		else:
			num = pow_2[fre[i]] - 1
			if num < 0:
				num += mod
			num = num * temp[-1] % mod
			temp.append(num)
	ans = 0
	for i in range(len(temp)):
		ans = (ans + temp[i] * pow_2[com[-1] - com[i + 1]] % mod * (i + 1)) % mod
	print(ans)


t = int(input())
MOD = 998244353
for tc in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = [0] * (n + 2)
	for i in l:
		if i <= n:
			cnt[i] += 1
	musthave = 1
	already = 0
	done = False
	ans = 0
	for i in range(1, n + 2):
		ans += i * (pow(2, n - cnt[i] - already, MOD) * musthave)
		ans %= MOD
		musthave *= pow(2, cnt[i], MOD) - 1
		musthave %= MOD
		already += cnt[i]
		if cnt[i] == 0:
			break
	print(ans)


import sys
import bisect as b
input = sys.stdin.readline
from collections import defaultdict as dd
mod = 1000000007
m = 998244353

def power(x, y):
	res = 1
	while y > 0:
		if y & 1 == 1:
			res = res * x
		y = y >> 1
		x = x * x
	return res
po = [0] * 100001
po[0] = 1
for i in range(1, 100001):
	po[i] = po[i - 1] * 2 % m
for _ in range(int(input())):
	n = int(input())
	d = {}
	l = list(map(int, input().split()))
	l.sort()
	for i in l:
		d[i] = d.get(i, 0) + 1
	key = list(d.keys())
	miss = 0
	for i in range(len(key)):
		if key[i] != i + 1:
			miss = i + 1
			break
	if miss == 0:
		miss = key[-1] + 1
	l = key
	s = 0
	x = 0
	y = 1
	for i in range(len(key)):
		c = po[n - d[l[i]] - x] * y
		y = y * (po[d[l[i]]] - 1)
		x += d[l[i]]
		if l[i] > miss:
			s += c * miss % m
		else:
			s += c * l[i] % m
	c = y * miss % m
	print((s + c) % m)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {n + 1: 0}
	for i in range(n):
		if d.get(l[i]) == None:
			d[l[i]] = 1
		else:
			d[l[i]] += 1
	if d.get(1) == None:
		print(pow(2, n, 998244353))
	else:
		rs = 0
		less = 1
		greater = 1
		c = 0
		for i in range(1, n + 2):
			if d.get(i) == None:
				d[i] = 0
			x = n - c - d.get(i)
			greater = pow(2, x, 998244353)
			c = c + d.get(i)
			ans = i * less * greater % 998244353
			rs += ans
			rs = rs % 998244353
			less = less * (pow(2, d.get(i)) - 1) % 998244353
		print(rs % 998244353)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	d = dict()
	for i in l:
		if d.get(i):
			d[i] = d[i] + 1
		else:
			d[i] = 1
	num = list()
	for i in range(1, 100002):
		if d.get(i):
			num.append(i)
		else:
			num.append(i)
			break
	fact = 1
	sum = 0
	for i in range(len(num) - 1):
		sum = int((sum + fact * num[i] % 998244353 * pow(2, n - d[num[i]], 998244353)) % 998244353)
		temp = pow(2, d[num[i]], 998244353) - 1
		if temp == -1:
			temp = 998244352
		fact = int(fact * temp % 998244353)
		n = n - d[num[i]]
	sum = int((sum + fact * num[len(num) - 1] % 998244353 * pow(2, n, 998244353)) % 998244353)
	print(sum)


MOD = 998244353
t = int(input())
for i in range(0, t):
	n = int(input())
	A = list(map(lambda x: int(x), input().split(' ')))
	dict = {}
	for a in A:
		if a in dict:
			dict[a] += 1
		else:
			dict[a] = 1
	mex = 1
	total = 0
	tot_perms = 1
	total_count = 0
	for num in sorted(dict.keys()):
		count = dict[num]
		total_count += count
		power = pow(2, n - total_count, MOD)
		total += mex * power * tot_perms
		tot_perms *= pow(2, count, MOD) - 1
		if num == mex:
			mex += 1
	total += mex * tot_perms
	print(total % MOD)


from collections import defaultdict
m = 998244353
for j in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = defaultdict(lambda : 0)
	for i in range(n):
		y[x[i]] += 1
	(finalsum, add, mex, mul) = (0, 0, 0, 1)
	for i in range(1, n + 1):
		mex = i * mul % m
		add = (add + y[i]) % m
		mex = mex * pow(2, n - add, m) % m
		finalsum = (finalsum + mex) % m
		mul = mul * (pow(2, y[i], m) - 1) % m
	print(finalsum)


def getmexum(n, arr):
	d = {}
	for i in arr:
		if i < n:
			if i not in d:
				d[i] = 0
			d[i] += 1
	mod = 998244353
	ans = 0
	pro = 1
	s = 0
	for i in range(10 ** 5 + 1):
		if i + 1 not in d:
			ans = (ans + (i + 1) * (pow(2, n - s, mod) * pro)) % mod
			break
		else:
			s = s + d[i + 1]
			ans = (ans + (i + 1) * pro * pow(2, n - s, mod)) % mod
			pro = pro * (pow(2, d[i + 1], mod) - 1) % mod
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	out = getmexum(n, arr)
	print(out)


T = int(input())

def pow(x):
	if x <= 0:
		return 1
	elif x == 1:
		return 2
	else:
		y = pow(x // 2)
		if x % 2 == 0:
			return y * y % 998244353
		else:
			return 2 * y * y % 998244353
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	s = 1
	l.sort()
	f = [0]
	c = [1]
	t = 0
	for i in range(N - 1):
		if l[i] == l[i + 1]:
			t += 1
		else:
			f.append(l[i])
			c.append(t + 1)
			t = 0
	if len(f) == 0 or f[-1] != l[-1]:
		f.append(l[-1])
		c.append(t + 1)
	k = 0
	i = 1
	t = 1
	while i < len(f) and i == f[i]:
		k += c[i]
		s = (s + t * i * pow(N - k)) % 998244353
		t = t * (pow(c[i]) - 1) % 998244353
		i += 1
	s = (s + t * i * pow(N - k)) % 998244353
	print(s - 1)


def power(x, n):
	if n == 0:
		return 1
	if n == 1:
		return x
	temp = power(x, n // 2)
	res = temp % mod * (temp % mod) % mod
	if n % 2 != 0:
		res = res * x % mod
	return res
t = int(input())
mod = 998244353
while t > 0:
	n = int(input())
	nums = list(map(int, input().split()))
	mex = n + 1
	freq = [0 for _ in range(mex + 2)]
	for i in range(n):
		nums[i] = mex + 1 if nums[i] > mex else nums[i]
		freq[nums[i]] += 1
	prefix = [1]
	for i in range(1, mex + 2):
		cur = (power(2, freq[i]) - 1) % mod
		res = cur * prefix[i - 1] % mod
		prefix.append(res)
	suffix = [0 for _ in range(mex + 2)]
	suffix[mex + 1] = freq[mex + 1]
	for i in range(mex, -1, -1):
		suffix[i] = suffix[i + 1] + freq[i]
	ans = 0
	for i in range(1, mex + 1):
		ex1 = prefix[i - 1]
		ex2 = suffix[i + 1]
		ex3 = power(2, ex2)
		res = ex1 * ex3 % mod
		cur_ans = res * i % mod
		ans = (ans + cur_ans) % mod
	print(ans)
	t -= 1


from collections import defaultdict
MOD = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	sequence = list(map(int, input().split()))
	frequency = defaultdict(int)
	for i in range(n):
		frequency[min(sequence[i], n + 1)] += 1
	sequence_length_covered = 0
	sum_of_all_mex = 0
	permutation_of_all_smaller_values = 1
	for i in range(1, n + 2):
		sequence_length_covered += frequency[i]
		sum_of_all_mex += pow(2, n - sequence_length_covered, MOD) * i % MOD * permutation_of_all_smaller_values % MOD
		if frequency[i] == 0:
			break
		else:
			permutation_of_all_smaller_values *= (pow(2, frequency[i], MOD) - 1) % MOD
	print(sum_of_all_mex % MOD)


T = int(input())
while T:
	N = int(input())
	A = [int(x) for x in input().split()]
	A.sort()
	B = {}
	for i in range(N):
		if A[i] < N:
			if A[i] not in B:
				B[A[i]] = 0
			B[A[i]] = B[A[i]] + 1
	s = 0
	p = 1
	mod = 998244353
	ans = 0
	for i in range(10 ** 5 + 1):
		if i + 1 not in B:
			ans = (ans + (i + 1) * pow(2, N - s, mod) * p) % mod
			break
		else:
			s = s + B[i + 1]
			ans = (ans + (i + 1) * pow(2, N - s, mod) * p) % mod
			p = p * (pow(2, B[i + 1], mod) - 1) % mod
	print(ans)
	T -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if l[i] < n:
			if l[i] not in d:
				d[l[i]] = 1
			else:
				d[l[i]] += 1
	p = 1
	ans = 0
	MOD = 998244353
	s = 0
	for i in range(10 ** 5 + 1):
		if i + 1 not in d:
			ans = (ans + (i + 1) * (p * pow(2, n - s, MOD))) % MOD
			break
		else:
			s = s + d[i + 1]
			ans = (ans + (i + 1) * p * pow(2, n - s, MOD)) % MOD
			p = p * (pow(2, d[i + 1], MOD) - 1) % MOD
	print(ans)


mod = 998244353
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	d = {}
	for i in range(0, n + 2):
		if i == 0:
			d[i] = 1
		else:
			d[i] = 0
	for i in range(0, n):
		if a[i] > n:
			a[i] = n + 1
		d[a[i]] = d[a[i]] + 1
	total = 0
	val = 1
	m = 0
	for i in range(1, n + 2):
		val = val * (pow(2, d[i - 1], mod) - 1)
		m = m + d[i]
		total = (total + i * pow(2, n - m, mod) * val) % mod
	print(total % mod)


from collections import Counter
for _ in range(int(input())):
	(n, ar) = (int(input()), list(map(int, input().split())))
	dic = Counter(ar)
	mod = 998244353
	rem = n
	left = 0
	right = 0
	mul = 1
	for num in range(1, n + 2):
		left = num * mul % mod
		rem = rem - dic[num]
		right = (right + left * pow(2, rem, mod)) % mod
		mul = mul * (pow(2, dic[num], mod) - 1) % mod
	print(right)


from collections import Counter
for _ in range(int(input())):
	(n, ar) = (int(input()), list(map(int, input().split())))
	dic = Counter(ar)
	mod = 998244353
	(add, mex, mul) = (0, 0, 1)
	finalsum = 0
	for num in range(1, n + 2):
		mex = mul * num % mod
		add = (add + dic[num]) % mod
		mex = mex * pow(2, n - add, mod) % mod
		finalsum = (finalsum + mex) % mod
		mul = mul * (pow(2, dic[num], mod) - 1) % mod
	print(finalsum)


from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect
import math
mod = 998244353
two = [1]
for i in range(1, 123456):
	two.append(two[-1] * 2)
	two[i] %= mod

def test_case():
	n = int(input())
	a = list(map(int, input().split()))
	cnt = {}
	for i in range(n):
		cnt[a[i]] = cnt.get(a[i], 0) + 1
	j = 1
	prev = 1
	ans = 0
	behind = 0
	while j <= n + 1:
		ans += j * prev * two[n - cnt.get(j, 0) - behind]
		prev *= (two[cnt.get(j, 0)] - 1) % mod
		behind += cnt.get(j, 0)
		ans %= mod
		if j not in cnt:
			break
		j += 1
	return ans
for _ in range(int(input())):
	ret = test_case()
	if ret:
		print(ret)


from collections import defaultdict
t = int(input())
N = 10 ** 5
m = 998244353
two = [1 for i in range(N + 1)]
for i in range(1, N + 1):
	two[i] = two[i - 1] * 2 % m
for _ in range(t):
	n = int(input())
	freq = defaultdict(lambda : 0)
	a = list(map(int, input().split()))
	if n == 1:
		if a[0] == 1:
			print(3)
		else:
			print(2)
	else:
		for i in range(n):
			if a[i] > n:
				a[i] = n
			freq[a[i]] += 1
		lans = 1
		lesseritems = 0
		total = 0
		for mex in range(1, n + 1):
			lans = lans % m * (two[freq[mex - 1]] - 1) % m % m if not mex == 1 else 1
			lesseritems += freq[mex - 1]
			greateritems = n - freq[mex] - lesseritems
			if greateritems < 0:
				break
			total = (total + mex * (lans % m * two[greateritems] % m) % m % m) % m
		print(total)


mod = 998244353
from collections import Counter
powers = [1]
for i in range(10 ** 5):
	powers.append(powers[-1] * 2 % mod)
for t in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	cnt = dict(Counter(a))
	sum_k = 0
	mult = 1
	res = 0
	for i in range(1, n + 2):
		ki = cnt.get(i, 0)
		sum_k += ki
		res = (res % mod + i % mod * (mult % mod) * powers[n - sum_k] % mod % mod) % mod
		mult = mult % mod * (powers[ki] - 1) % mod % mod
	print(res)


import math
from sys import stdin, stdout
from functools import lru_cache
from collections import Counter
T = int(stdin.readline())
for i in range(T):
	N = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	res = [0]
	dc = Counter(arr)
	ans = 0
	pr = 1
	sm = 0
	z = 0
	for mex in range(1, N + 2):
		c = dc.get(mex, 0)
		z += c
		sm = pow(2, N - z, 998244353)
		sm = sm * pr * mex
		pr = pr * (pow(2, c, 998244353) - 1) % 998244353
		ans += sm
		ans = ans % 998244353
	print(ans)


from sys import stdin, stdout
from collections import defaultdict
T = int(stdin.readline())
for i in range(T):
	N = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	res = [0]
	dc = defaultdict(lambda : 0)
	for nm in arr:
		dc[nm] += 1
	ans = 0
	pr = 1
	sm = 0
	z = 0
	for mex in range(1, N + 2):
		c = dc[mex]
		z += c
		sm = pow(2, N - z, 998244353)
		sm = sm * pr * mex
		pr = pr * (pow(2, c, 998244353) - 1) % 998244353
		ans += sm
		ans = ans % 998244353
	print(ans)


from collections import defaultdict
t = int(input())
mod = 998244353
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = defaultdict(lambda : 0)
	for i in range(n):
		cnt[a[i]] += 1
	su = 0
	prd = 1
	final_sum = 0
	for i in range(1, n + 1):
		su = (su + cnt[i]) % mod
		res = i * prd % mod
		res = res % mod * pow(2, n - su, mod) % mod
		final_sum = (final_sum + res) % mod
		prd = prd % mod * (pow(2, cnt[i], mod) - 1) % mod % mod
	print(final_sum)


from collections import Counter
mod = 998244353
two = [1]
for i in range(1, 100017):
	two.append(two[len(two) - 1] * 2 % mod)
test = int(input())
while test:
	n = int(input())
	v = list(map(int, input().split()))
	sorted(v)
	u = list(set(v))
	sorted(u)
	occurance = Counter(v)
	diff = n + 1
	for i in range(1, n + 1):
		if occurance[i] == 0:
			diff = i
	sum = 0
	product = 1
	ans = 0
	for i in range(1, diff + 1):
		value = n - sum - occurance[i]
		ans = (ans + i * product * two[value]) % mod
		sum += occurance[i]
		product *= two[occurance[i]] - 1
	print(ans)
	test -= 1


from collections import Counter
MAX = 1000001
MOD = 998244353
powers = [1]
for x in range(1, MAX):
	powers.append(powers[-1] * 2 % MOD)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	cnt = dict(Counter(arr))
	mx = 1
	while mx in cnt:
		mx += 1
	if mx == 1:
		print(powers[n] % MOD)
		continue
	cnt[mx] = 0
	countTill = [0, cnt[1]]
	product = [0, (powers[cnt[1]] - 1) % MOD]
	for i in range(2, mx, 1):
		countTill.append(countTill[-1] + cnt[i])
		product.append(product[-1] * ((powers[cnt[i]] - 1) % MOD) % MOD)
	ans = {}
	ans[1] = powers[n - cnt[1]] % MOD
	for i in range(2, mx + 1, 1):
		ans[i] = product[i - 1] * powers[n - countTill[i - 1] - cnt[i]] % MOD
	final = 0
	for k in ans:
		final = (final + k * ans[k] % MOD) % MOD
	print(final)


from collections import Counter
mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	f = Counter(a)
	b = set(f)
	holes = {i for i in range(1, n + 2)}
	holes = holes - b
	hole = min(holes)
	b = list(b)
	b.sort()
	sum = 0
	pre = 1
	es = n
	tmp = 1
	for i in b:
		pre = pre * tmp % mod
		mex = min(hole, i)
		if mex >= mod:
			mex -= mod
		es -= f[i]
		suf = pow(2, es, mod)
		sum += mex * pre % mod * suf % mod
		sum %= mod
		tmp = (pow(2, f[i], mod) - 1) % mod
	pre = pre * tmp % mod
	sum += hole * pre % mod
	sum %= mod
	print(sum)


mod = 998244353

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	cnt = [0 for i in range(n + 2)]
	for i in a:
		if i <= n + 1:
			cnt[i] += 1
	curr = 1
	total = 0
	ans = 0
	for i in range(1, n + 2):
		total += cnt[i]
		ans = (ans + power(2, n - total, mod) * curr % mod * i % mod) % mod
		curr = curr * (power(2, cnt[i], mod) - 1 + mod) % mod
	print(ans)


M = 998244353
pow2 = [1]
for i in range(10 ** 5 + 1):
	pow2.append(pow2[i] * 2 % M)
for t in range(int(input().strip())):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	d = dict()
	freq = [0 for i in range(n + 5)]
	for i in arr:
		freq[min(i, n + 1)] += 1
	ans = 0
	prod = 1
	sf = [0 for i in range(n + 5)]
	for i in range(n + 3, -1, -1):
		sf[i] = sf[i + 1] + freq[i]
	for mex in range(1, n + 1):
		ans = (ans + mex * prod * pow2[sf[mex + 1]]) % M
		prod = prod * (pow2[freq[mex]] - 1) % M
	print(ans)


from collections import Counter
I = input
M = 998244353
t = int(I())
for _ in range(t):
	n = int(I())
	c = Counter(map(int, I().split()))
	p = c[0] = 1
	i = r = 0
	while c[i]:
		i += 1
		n -= c[i]
		r = (r + i * p * pow(2, n, M)) % M
		p = p * (pow(2, c[i], M) - 1) % M
	print(r)


powerr = 998244353
import collections
from collections import OrderedDict

def cf(arr):
	return OrderedDict(collections.Counter(arr))

def mexum(s, n):
	if s[n - 1] != 1:
		return pow(2, n, powerr)
	freq = cf(s)
	curr = 1
	contfreq = 0
	next = 1
	pres = 1
	key = 1
	totfreq = 0
	for key in freq:
		totfreq += freq[key]
	while pres:
		if key in freq:
			contfreq += freq[key]
			next = key + 1
			key += 1
		else:
			pres = 0
	rem = n - contfreq
	curr = 1
	done = 0
	minus = 1
	tot = 0
	i = 1
	pres = 1
	f = 0
	key = 1
	while pres and f < n:
		if key in freq:
			nextval = key
			done += freq[key]
			tot += pow(2, totfreq - done, powerr) * nextval * minus
			tot %= 998244353
			nextval += 1
			minus *= pow(2, freq[key], powerr) - 1
			key += 1
		else:
			tot += pow(2, rem, powerr) * nextval * minus
			tot %= 998244353
			break
		f += 1
	return int(tot) % 998244353
t = int(input())
for q in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sorted(l)[::-1]
	print(mexum(s, n))


mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(s) for s in input().split()]
	x = list(set(a))
	x.sort()
	d = {}
	z = 1
	for i in range(len(x)):
		if z == x[i]:
			z += 1
		else:
			break
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = 1
		else:
			d[a[i]] += 1
	j = 1
	i = 0
	r = 0
	s = n - d[x[0]]
	n1 = len(x)
	while i < n1 and z > 1:
		if x[i] != j:
			r += pow(2, s, mod) * y * j
			break
		if i == 0:
			r += pow(2, s, mod)
			y = pow(2, d[1], mod) - 1
			r %= mod
			j += 1
			i += 1
		else:
			s -= d[x[i]]
			h = y * pow(2, s, mod)
			h %= mod
			r += h * j % mod
			y *= pow(2, d[x[i]], mod) - 1
			y %= mod
			j += 1
			i += 1
	if i == n1:
		r += pow(2, s, mod) * y * j
	if z == 1:
		r += pow(2, n, mod) % mod
	print(r % mod)


from collections import Counter
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = Counter(arr)
	k = 1
	ans = 0
	pre = 1
	pre_c = 0
	while 1:
		if arr[k] == 0:
			ans += k * pre * pow(2, n - pre_c, mod)
			ans %= mod
			break
		pre_c += arr[k]
		ans += k * pre * pow(2, n - pre_c, mod)
		ans %= mod
		pre *= 2 ** arr[k] - 1
		k += 1
	print(ans)


mod = 998244353
import sys
from collections import defaultdict as dc
input = sys.stdin.readline

def solve(n, l, d):
	for i in range(n):
		d[l[i]] += 1
	for i in range(1, 10 ** 5 + 1):
		if d[i] == 0:
			res = i
			break
	(ans1, RESULT) = (1, 0)
	ans2 = 0
	for i in range(1, res + 1):
		RESULT += d[i]
		temp = pow(2, n - RESULT, mod)
		ans2 += i * (ans1 * temp) % mod % mod
		ans1 = ans1 * (pow(2, d[i], mod) - 1)
	return ans2 % mod
test = int(input())
for _ in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	d = dc(lambda : 0)
	res = 0
	print(solve(n, l, d))


import collections
import sys
t = int(input())
p = 998244353
while t:
	t -= 1
	n = int(input())
	twon = n
	m = {}
	a = [int(x) for x in input().split()]
	for aa in a:
		if aa not in m:
			m[aa] = 0
		m[aa] += 1
	sum = 0
	m = collections.OrderedDict(sorted(m.items()))
	i = 1
	for key in m:
		if key != i:
			break
		else:
			i += 1
	prod = 1
	for key in m:
		if key > i:
			break
		twon -= m[key]
		sum += key * pow(2, twon, p) * prod % p
		prod = prod * (pow(2, m[key], p) - 1) % p
	sum += i * prod * pow(2, twon, p)
	print(sum % p // 1)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as c
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

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

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(int(data())):
	n = int(data())
	arr = l()
	arr.sort()
	if arr[0] != 1:
		outln(pow(2, n, mod2))
		continue
	(dp, new) = (c(arr), [])
	new.append(arr[0])
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			new.append(arr[i])
	(s, p) = ([], [])
	(add, mul) = (0, 1)
	for i in range(len(new)):
		mul = mul * (pow(2, dp[new[i]], mod2) - 1) % mod2
		add = (add + dp[new[i]]) % mod2
		s.append(add)
		p.append(mul)
	answer = pow(2, n - dp[arr[0]], mod2)
	result = True
	for i in range(1, len(new)):
		if new[i] != i + 1:
			answer = (answer + p[i - 1] * pow(2, n - s[i - 1], mod2) * (i + 1)) % mod2
			result = False
			break
		else:
			answer = (answer + p[i - 1] * pow(2, n - s[i], mod2) * new[i]) % mod2
	if result:
		answer = (answer + p[len(new) - 1] * (len(new) + 1)) % mod2
	outln(answer)


from bisect import bisect_left as bl, bisect_right as br
from collections import defaultdict as dd
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	d = dd(int)
	for i in range(n):
		d[l[i]] += 1
	l1 = list(d.keys())
	l1.sort()
	k = 1
	while True:
		if d[k] == 0:
			break
		k += 1
	sm = 0
	l2 = [1]
	for i in l1:
		l2.append(l2[-1] * (pow(2, d[i], mod) - 1) % mod)
	for i in range(1, k + 1):
		ctd = bl(l, i)
		ctu = n - br(l, i)
		sm1 = l2[i - 1]
		sm = (sm + i * pow(2, ctu, mod) * sm1) % mod
	print(sm)


mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	dp = {}
	for i in range(n):
		if i == 0:
			if a[0] == 1:
				dp[1] = 1
				dp[2] = 1
				ans = 3
			else:
				dp[1] = 2
				ans = 2
		else:
			if a[i] not in dp:
				dp[a[i]] = 0
			ans = ans * 2 % mod
			ans = mod + ans - a[i] % mod * (dp[a[i]] % mod) % mod
			ans = (ans + dp[a[i]] % mod * ((1 + a[i]) % mod) % mod) % mod
			if a[i] + 1 not in dp:
				dp[a[i] + 1] = 0
			dp[a[i] + 1] *= 2
			dp[a[i] + 1] %= mod
			dp[a[i] + 1] = (dp[a[i] + 1] + dp[a[i]]) % mod
	print(ans)


mod = 998244353

def power(a, n, m):
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * a % m
		a = a * a % m
		n //= 2
	return res
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	dp = [0 for i in range(n + 1)]
	m = dict()
	for i in arr:
		if i in m:
			m[i] += 1
		else:
			m[i] = 1
	dp[0] = 1
	for i in range(1, n + 1):
		if i not in m:
			break
		else:
			dp[i] = dp[i - 1] * (power(2, m[i], mod) - 1) % mod % mod
	(k, cnt) = (1, 0)
	res = 0
	for i in range(1, n + 1):
		if i not in m:
			k = dp[i - 1] % mod
			if n - cnt != 0:
				k = k * power(2, n - cnt, mod) % mod
			res = (res + i * k % mod) % mod
			break
		k = dp[i - 1] % mod
		cnt += m[i]
		if n - cnt != 0:
			k = k * power(2, n - cnt, mod) % mod
		res = (res + i * k % mod) % mod
	print(res)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	mod = 998244353
	ans = 0
	curr = 1
	one = 0
	freq = defaultdict(int)
	for num in arr:
		freq[num] += 1
	mul = defaultdict(int)
	mul[0] = 1
	while curr in freq:
		mul[curr] = mul[curr - 1] * (pow(2, freq[curr], mod) - 1)
		mul[curr] %= mod
		curr += 1
	j = 0
	for i in range(curr + 1):
		while j < n and arr[j] <= i:
			j += 1
		right = n - j
		temp = i * mul[i - 1] * pow(2, right, mod)
		temp %= mod
		ans += temp
		ans %= mod
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = [int(i) for i in input().split()]
	elemCounts = {}
	for num in arr:
		if num in elemCounts:
			elemCounts[num] += 1
		else:
			elemCounts[num] = 1
	nums = sorted(elemCounts.keys())
	currVal = 1
	opVal = 1
	if nums[0] != 1:
		print(pow(2, N, 998244353))
	else:
		sum = 0
		countTillHere = 0
		mulTillHere = 1
		brkDet = False
		for i in range(len(nums)):
			if nums[i] != opVal:
				sum = (sum + opVal * pow(2, N - countTillHere, 998244353) * mulTillHere % 998244353) % 998244353
				brkDet = True
				break
			else:
				countTillHere += elemCounts[nums[i]]
				sum = (sum + opVal * pow(2, N - countTillHere, 998244353) * mulTillHere % 998244353) % 998244353
				mulTillHere = mulTillHere * (pow(2, elemCounts[nums[i]], 998244353) - 1) % 998244353
				opVal = nums[i] + 1
		if brkDet:
			print(sum)
		else:
			sum = (sum + opVal * pow(2, N - countTillHere, 998244353) * mulTillHere % 998244353) % 998244353
			print(sum)


m = 998244353
p2 = [1]
p = 1
for i in range(10 ** 5 + 1):
	p2.append(p % m * (2 % m) % m)
	p *= 2
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = [0] * (n + 1)
	for i in range(n):
		if a[i] <= n:
			cnt[a[i]] += 1
	mark = 0
	c = []
	for i in range(1, n + 1):
		if cnt[i] == 0:
			mark = i
			break
		else:
			c.append(cnt[i])
	l = 0
	ans = 0
	t = 1
	for i in range(len(c)):
		l += c[i]
		if i == 0:
			ans += p2[n - l] % m
			ans = ans % m
			t = t % m * (p2[c[i]] - 1) % m % m
			t = t % m
		else:
			ans += (i + 1) % m * t % m * p2[n - l] % m % m
			ans = ans % m
			t = t % m * (p2[c[i]] - 1) % m % m
			t = t % m
	ans += t % m * (p2[n - l] % m) * (len(c) + 1) % m % m
	print(ans % m)


m = 998244353
T = int(input())
for _ in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	dic = dict()
	for i in range(n):
		if l[i] not in dic.keys():
			dic[l[i]] = 1
		else:
			dic[l[i]] += 1
	uni = list(dic.keys())
	uni.sort()
	missing = 1
	for i in range(len(uni)):
		if uni[i] != missing:
			break
		else:
			missing += 1
	xx = []
	for num in uni:
		xx.append(dic[num])
	X = sum(xx[missing - 1:])
	remain = pow(2, X, m)
	xx = xx[0:missing - 1]
	if len(xx):
		simple = [1, 1]
		simple1 = [1]
		cnt = n
		for i in range(len(xx) - 1, 0, -1):
			simple.append(simple[-1] % m * (pow(2, xx[i]) % m) % m)
		simple = simple[::-1]
		for i in range(len(xx)):
			simple1.append(simple1[-1] % m * ((pow(2, xx[i]) - 1) % m) % m)
		ans = 0
		for i in range(len(simple)):
			ans = ((i + 1) % m * (simple[i] % m) * (simple1[i] % m) * (remain % m) % m + ans % m) % m
		print(ans)
	else:
		print(remain)


m = 998244353

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	count = [0 for _ in range(n + 2)]
	for a_i in arr:
		count[min(n + 1, a_i)] += 1
	pow_array1 = [pow(2, n_i, m) for n_i in count]
	pow_array2 = [(p_i - 1) % m for p_i in pow_array1]
	l_product = [1 for _ in range(n + 2)]
	for i in range(2, n + 2):
		l_product[i] = l_product[i - 1] * pow_array2[i - 1] % m
	r_product = [1 for _ in range(n + 2)]
	for i in range(n, 0, -1):
		r_product[i] = r_product[i + 1] * pow_array1[i + 1] % m
	total_sum = 0
	for i in range(1, n + 1):
		total_sum += i * (l_product[i] * r_product[i]) % m % m
		total_sum %= m
	print(total_sum)
t = int(input())
for _ in range(t):
	main()


mod = 998244353

def pow(x, n):
	if w[n] != 0:
		return w[n]
	else:
		t = pow(x, n // 2)
		if n % 2 == 0:
			k = t * t % mod
		else:
			k = 2 * t * t % mod
		w[n] = k
		return k
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	w = [0 for i in range(n + 1)]
	(w[0], w[1]) = (1, 2)
	if l[0] > 1:
		print(pow(2, n))
	else:
		k = [0]
		i = 1
		j = 0
		while j < n:
			count = 0
			while l[j] == i:
				count += 1
				j += 1
				if j == n:
					break
			if count == 0:
				break
			else:
				k.append(count)
				i += 1
		t = n - k[1]
		count = pow(2, t)
		rem = pow(2, n) - count
		pro = pow(2, k[1]) - 1
		for j in range(2, i):
			t -= k[j]
			r = pro * pow(2, t)
			count += j * r % mod
			rem -= r
			pro *= pow(2, k[j]) - 1
		count += i * rem % mod
		print(count % mod)


t = int(input().strip())
m = 998244353

def fast_exp(n):
	if n == 0:
		return 1
	ans = fast_exp(n // 2)
	ans = ans * ans % m
	if n % 2 == 1:
		ans = 2 * ans % m
	return ans
for _ in range(t):
	n = int(input().strip())
	counts = {}
	a = [int(x) for x in input().strip().split()]
	for el in a:
		if el not in counts:
			counts[el] = 1
		else:
			counts[el] += 1
	p = 1
	ans = 0
	for x in range(1, 100001):
		c = 0
		if x in counts:
			c = counts[x]
		y = fast_exp(n - c) * p % m
		ans = (ans + y * x % m) % m
		p = p * (fast_exp(c) - 1) % m
		n -= c
		if x not in counts:
			break
	print(ans)


import sys
mod = 998244353
input = sys.stdin.readline
from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	Hash = defaultdict(lambda : 0)
	for i in L:
		Hash[i] += 1
	maxans = 0
	for i in range(1, 10 ** 5 + 1):
		if Hash[i] == 0:
			maxans = i
			break
	ektohlelo = 1
	curr = 0
	ans = 0
	for i in range(1, maxans + 1):
		curr += Hash[i]
		lelo = pow(2, N - curr, mod)
		ans += i * (ektohlelo * lelo) % mod % mod
		ektohlelo = ektohlelo * (pow(2, Hash[i], mod) - 1)
	print(ans % mod)


def main():
	p = 998244353
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		a.sort()
		l = [0] * (n + 1)
		for i in a:
			if i - 1 < n:
				l[i - 1] += 1
		s = 0
		x = n
		rem = 1
		u = []
		q = -1
		for i in range(n):
			if l[i] != 0:
				x -= l[i]
				s = (s + (i + 1) * (rem * pow(2, x, p) % p) % p) % p
				u.append(l[i])
				rem = rem * ((pow(2, l[i]) - 1) % p) % p
			else:
				q = i
				break
		if q != -1:
			s = (s + rem * ((i + 1) * pow(2, x, p) % p) % p) % p
		print(s)
main()


mod = 998244353
power = [1]
for i in range(1, 500001):
	power.append(power[i - 1] * 2 % mod)
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	ans = 0
	s.sort()
	dict = {}
	pict = {}
	for i in range(n):
		if dict.get(s[i]) is None:
			dict[s[i]] = 0
		dict[s[i]] += 1
		pict[s[i]] = i
	index = 0
	for i in range(len(s)):
		if s[i] == 1:
			index += 1
		else:
			break
	ans += power[n - index] * 1
	ans = ans % mod
	p = 1
	count = 0
	while True:
		if count >= 1:
			if pict.get(count + 1) is None:
				q = n - pict[count] - 1
			else:
				q = n - pict[count + 1] - 1
			ans += p * power[q] * (count + 1)
			ans = ans % mod
		if dict.get(count + 1) is None:
			break
		count += 1
		p = p * (power[dict[count]] - 1)
	print(ans)


import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
input = sys.stdin.readline
write = sys.stdout.write
MOD = 998244353
T = int(input())
for _ in range(T):
	n = int(input())
	nums = [int(s) for s in input().split()]
	if min(nums) != 1:
		print(pow(2, n, MOD))
		continue
	cnt = Counter(nums)
	limit = 1
	remain = n
	for num in sorted(cnt):
		if num == limit:
			remain -= cnt[num]
			limit += 1
		else:
			break
	prefix = [1]
	for i in range(1, limit):
		prefix.append(prefix[-1] * (pow(2, cnt[i], MOD) - 1) % MOD)
	suffix = [1]
	for i in range(1, limit)[::-1]:
		suffix.append(suffix[-1] * pow(2, cnt[i], MOD) % MOD)
	suffix = suffix[::-1] + [1]
	ans = 0
	for i in range(1, limit + 1):
		ans += i * prefix[i - 1] * suffix[i]
		ans %= MOD
	print(ans * pow(2, remain, MOD) % MOD)


import sys
from collections import *
from bisect import *
input = sys.stdin.readline
t = int(input())
p = 998244353
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	f = Counter(a)
	s = 0
	x = len(f)
	if 1 in f:
		s += pow(2, n - f[1], p) - 1
	else:
		s += pow(2, n, p) - 1
		print((s + 1) % p)
		continue
	c = 2
	flag = 0
	x = 1
	fac = 0
	while 1:
		if c - 1 not in f:
			break
		x *= pow(2, f[c - 1], p) - 1
		fac += f[c - 1]
		if c in f:
			z = f[c]
		else:
			z = 0
		y = pow(2, n - fac - z, p)
		s += x * c * y % p
		c += 1
	print((s + 1) % p)


t = int(input())
for you in range(t):
	n = int(input())
	arr = [0 for i in range(n + 1)]
	l = input().split()
	li = [int(i) for i in l]
	for i in li:
		if i <= n:
			arr[i - 1] += 1
	sumi = 0
	pro = 1
	prefsum = 0
	for i in range(n + 1):
		if ():
			break
		else:
			prefsum += arr[i]
			sumi = sumi + (i + 1) * pow(2, n - prefsum, 998244353) * pro % 998244353
			sumi = sumi % 998244353
			if arr[i] == 0:
				break
			t = pow(2, arr[i], 998244353)
			if t < 1:
				t += 998244353
			pro = pro * (t - 1) % 998244353
	print(sumi)