Let's define Score of an array B of length M as \sum_{i=1}^{M} \sum_{j=i}^{M} f(i,j), where f(i,j) = B_{i} | B_{i+1} | \dots | B_{j} (Here | denotes the [bitwise OR operation]

You are given an array A, consisting of N distinct elements.

Find the sum of Score over all N! possible permutations of A.

Since the answer can be large, output it modulo 998244353.

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

- The first line of input contains a single integer T - the number of test cases. The description of T test cases follow.
- The first line of each test case contains an integer N - the length of the array.
- The second line of each test case contains N space-separated distinct integers A_{1},A_{2}, \dots ,A_{n} representing the array A.

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

For each test case, output the sum obtained modulo 998244353.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i}  < 2^{30}$
- Sum of $N$ does not exceed $5 \cdot 10^{5}$ over all testcases

----- Sample Input 1 ------ 
2
2
2 3
4
343 10 7 47
----- Sample Output 1 ------ 
16
47160

----- explanation 1 ------ 
Test Case 1: Two permutations of $A$ are $[2,3]$ and $[3,2]$. 

- $Score$ of $[2, 3] = f(1, 1) + f(2, 2) + f(1, 2) = 2 + 3 + 2$ $|$ $3 = 8$.
- $Score$ of $[3, 2] = f(1, 1) + f(2, 2) + f(1, 2) = 3 + 2 + 3$ $|$ $2 = 8$. 

So, the required sum is $16$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Combinatorics

Mathematics


Solutions:
import math as mt

def get_input(f):
	if f is None:
		nextline = input()
	else:
		nextline = f.readline()
	return nextline

def ORSUM():
	read_from_file = 0
	if read_from_file:
		f = open('input.txt', 'r')
	else:
		f = None
	factDict = {0: 1, 1: 1}
	invDict = {1: 1, 2: 499122177}
	maxFact = 1
	maxInv = 2
	bigM = 998244353
	for _ in range(int(get_input(f))):
		n = int(get_input(f))
		nums = list(map(int, get_input(f).split()))
		calcFact(factDict, invDict, maxFact, n + 2, maxInv, n + 2, bigM)
		maxFact = n + 2
		maxInv = n + 2
		maxN = max(nums)
		if maxN == 0:
			print(0)
			return
		maxK = mt.ceil(mt.log2(maxN + 1))
		kDict = {}
		for k in range(maxK):
			kDict[k] = 0
		for i in range(n):
			thisB = format(nums[i], 'b')
			thisB = thisB[::-1]
			for j in range(len(thisB)):
				if thisB[j] == '1':
					kDict[j] += 1
		currMult = 1
		total = 0
		for i in range(maxK):
			thisK = kDict[i]
			thisTerm = factDict[n + 2] * thisK % bigM
			thisTerm = thisTerm * invDict[thisK + 2] % bigM
			thisTerm = thisTerm * invDict[2] % bigM
			thisTerm = thisTerm * currMult % bigM
			total = (total + thisTerm) % bigM
			currMult = currMult * 2 % bigM
		print(total)

def calcFact(factDict, invDict, maxFact, newMax, maxInv, newMaxInv, bigM):
	currFact = factDict[maxFact]
	for i in range(maxFact + 1, newMax + 1):
		currFact = currFact * i % bigM
		factDict[i] = currFact
	for i in range(maxInv + 1, newMaxInv + 1):
		invDict[i] = modInverse(i, bigM)

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
ORSUM()