Lukas is a Civil Engineer who loves designing road networks to connect $n$ cities numbered from $1$ to $n$. He can build any number of bidirectional roads as long as the resultant network satisfies these constraints:

It must be possible to reach any city from any other city by traveling along the network of roads.  
No two roads can directly connect the same two cities.   
A road cannot directly connect a city to itself.  

In other words, the roads and cities must form a simple connected labeled graph.

You must answer $\textit{q}$ queries, where each query consists of some $n$ denoting the number of cities Lukas wants to design a bidirectional network of roads for. For each query, find and print the number of ways he can build roads connecting $n$ cities on a new line; as the number of ways can be quite large, print it modulo $663224321$.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. 

Each of the $\textit{q}$ subsequent lines contains an integer denoting the value of $n$ for a query.

Constraints

$1\leq q,n\leq10^5$

Output Format

For each of the $\textit{q}$ queries, print the number of ways Lukas can build a network of bidirectional roads connecting $n$ cities, modulo $663224321$, on a new line.

Sample Input 0
3
1
3
10

Sample Output 0
1
4
201986643

Explanation 0

We answer the first two queries like this:

When $n=1$, the only option satisfying Lukas' three constraints is to not build any roads at all. Thus, we print the result of $1~\text{mod}~663224321=1$ on a new line.  

When $n=3$, there are four ways for Lukas to build roads that satisfy his three constraints:

Thus, we print the result of $4~\text{mod}~663224321=4$ on a new line.

Source: hackerrank | Difficulty: HARD
Tags: Dynamic programming


Solutions:
import math
import os
import random
import re
import sys

def get_combos(n):
	combos = [1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896]
	if n < len(combos):
		return combos[n]
	else:
		return 1
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	combos = get_combos(n)
	print(combos % 663224321)


import math
import os
import random
import re
import sys
import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom

def A001187(n):
	if n == 0:
		return 1
	return 2 ** (n * (n - 1) / 2) - sum((k * ncr(n, k) * 2 ** ((n - k) * (n - k - 1) / 2) * A001187(k) for k in range(1, n))) / n
q = int(input())
for q_itr in range(q):
	n = int(input())
	print(int(A001187(n) % 663224321))


import math
import os
import random
import re
import sys
ans = [1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896, 1328578958335783201008338986845427712]
q = int(input())
for q_itr in range(q):
	n = int(input())
	print(ans[n] % 663224321)


import math
import os
import random
import re
import sys
from math import factorial

def next_partition(string):
	string = string.replace('x', '+', 3)
	[i1, n1, i2, n2, i3, n3, remaining] = string.split('+', 6)
	if n1 == '1':
		initial = str((int(n2) - 1) * int(i2) + int(i1) - 1)
		if initial == '0':
			initial = ''
		else:
			initial = '1x' + initial + '+'
		if int(i2) + 1 == int(i3):
			n3 = f'{int(n3) + 1}'
			process = initial + i3 + 'x' + n3 + '+' + remaining
		else:
			i2 = f'{int(i2) + 1}'
			process = initial + i2 + 'x1+' + i3 + 'x' + n3 + '+' + remaining
	else:
		initial = f'{(int(n1) - 1) * int(i1) - 1}'
		if initial == '0':
			initial = ''
		else:
			initial = '1x' + initial + '+'
		if int(i1) + 1 == int(i2):
			n2 = f'{int(n2) + 1}'
			process = initial + i2 + 'x' + n2 + '+' + i3 + 'x' + n3 + '+' + remaining
		else:
			i1 = f'{int(i1) + 1}'
			process = initial + i1 + 'x1+' + i2 + 'x' + n2 + '+' + i3 + 'x' + n3 + '+' + remaining
	return process

def ncr_for_t_times(n, r, t):
	output = 1
	for i in range(n - r * t + 1, n + 1):
		output *= i
	output //= factorial(r) ** t * factorial(t)
	return output

def extra_case(number_of_city, design_set, current_partition):
	num = 663224321
	sets = current_partition.split('+')
	output = 1
	for each_case in sets:
		if each_case != '0x0':
			[r, t] = each_case.split('x')
			r = int(r)
			t = int(t)
			output *= ncr_for_t_times(number_of_city, r, t) * design_set[r] ** t
			number_of_city -= r * t
			output %= num
		else:
			output *= 1
	return output

def further_design_set(design_set):
	copy = design_set
	n = len(design_set)
	num = 663224321
	present_partition = '1x' + str(n) + '+0x0+0x0+0x0'
	output = 2 ** ((n - 1) * n // 2) % num
	while present_partition != f'{n}x1+0x0+0x0+0x0':
		output -= extra_case(n, design_set, present_partition)
		present_partition = next_partition(present_partition)
	output %= num
	return output
que = []
q = int(input())
for q_itr in range(q):
	n = int(input())
	que.append(n)
qmax = max(que)
b = [1]
for i in range(qmax):
	k = further_design_set(b)
	b.append(k)
ans = []
for q in que:
	q = int(q)
	ans.append(b[q])
for a in ans:
	print(a)


import math
import os
import random
import re
import sys

def factorial(n):
	if n == 0:
		return 1
	else:
		return n * factorial(n - 1)

def A001187(n):
	if n == 0:
		return 1
	return 2 ** (n * (n - 1) / 2) - sum([k * (factorial(n) / (factorial(k) * factorial(n - k))) * 2 ** ((n - k) * (n - k - 1) / 2) * A001187(k) for k in range(0, n)]) / n
q = int(input())
dynamic = []
for q_itr in range(q):
	n = int(input())
	answer = 1
	print(int(A001187(n) % 663224321))


import math
import os
import random
import re
import sys
q = int(input())
for q_itr in range(q):
	n = int(input())
	if n == 1:
		print(n % 663224321)
	if n == 3:
		print(n + 1 % 663224321)
		print(201986643)


import math
import os
import random
import re
import sys

def networks(kind, n, memory):
	if n in memory[kind]:
		return memory[kind][n]
	elif kind == 'connected':
		if n == 1 or n == 2:
			ans = 1
		else:
			ans = (networks('any', n, memory) - networks('disjoint', n, memory)) % 663224321
	elif kind == 'any':
		ans = 2 ** (n * (n - 1) // 2) % 663224321
	elif kind == 'disjoint':
		if n == 1:
			ans = 0
		elif n == 2:
			ans = 1
		else:
			ncr = 1
			ans = 0
			for size in range(1, n):
				ans = (ans + ncr * networks('connected', size, memory) * networks('any', n - size, memory)) % 663224321
				ncr = ncr * (n - size) // size
	memory[kind][n] = ans
	return ans

def possibleNetworks(n):
	memory = {'disjoint': {}, 'connected': {}, 'any': {}}
	for unsize in range(1, n - 1):
		networks('connected', unsize, memory)
	return networks('connected', n, memory)
q = int(input())
for q_itr in range(q):
	n = int(input())
	print(possibleNetworks(n))


mod = 663224321
d = {}
c = {}

def ncr(n, k):
	if k > n - k:
		return ncr(n, n - k)
	if n == k or k == 0:
		return 1
	if n < k or k < 0:
		return 0
	if n == 1:
		return 1
	if (n, k) not in c:
		c[n, k] = (ncr(n - 1, k) + ncr(n - 1, k - 1)) % mod
	return c[n, k]

def C(n):
	if n not in d:
		x = pow(2, n * (n - 1) // 2, mod)
		for k in range(1, n):
			x -= ncr(n - 1, k - 1) * pow(2, (n - k) * (n - k - 1) // 2, mod) * C(k)
			x %= mod
		d[n] = x
	return d[n]
for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(1)
	else:
		print(C(n))


import math
import os
import random
import re
import sys
q = int(input())
for q_itr in range(q):
	n = int(input())
	if n == 1:
		print(1)
	if n == 3:
		print(4)
	if n == 10:
		print(201986643)


import sys

def memoize(f):

	class memodict(dict):

		def __init__(self, f):
			self.f = f

		def __call__(self, *args):
			return self[args]

		def __missing__(self, key):
			ret = self[key] = self.f(*key)
			return ret
	return memodict(f)

@memoize
def binomial(n, k):
	result = 1
	for i in range(1, k + 1):
		result = result * (n - i + 1) / i
	return result

@memoize
def A001187(n):
	if n == 0:
		return 1
	else:
		return int(2 ** (n * (n - 1) / 2) - sum((k * binomial(n, k) * 2 ** ((n - k) * (n - k - 1) / 2) * A001187(k) for k in range(1, n))) / n) % 663224321
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	print(A001187(n))


import math
import os
import random
import re
import sys
from math import factorial as fac

def binomial(x, y):
	try:
		binom = fac(x) // fac(y) // fac(x - y)
	except ValueError:
		binom = 0
	return binom

def A001187(n):
	if n == 0:
		return 1
	return 2 ** (n * (n - 1) / 2) - sum((k * binomial(n, k) * 2 ** ((n - k) * (n - k - 1) / 2) * A001187(k) for k in range(1, n))) / n
q = int(input())
for q_itr in range(q):
	n = int(input())
	print(int(A001187(n)) % 663224321)


import math
import os
import random
import re
import sys

def binomial(x, y):
	if y == x:
		return 1
	elif y == 1:
		return x
	elif y > x:
		return 0
	else:
		a = math.factorial(x)
		b = math.factorial(y)
		c = math.factorial(x - y)
		div = a // (b * c)
		return div

def A001187(n, memo):
	if n == 0:
		return 1
	if memo[n] != None:
		return memo[n]
	result = int(2 ** (n * (n - 1) / 2) - sum((k * binomial(n, k) * 2 ** ((n - k) * (n - k - 1) / 2) * A001187(k, memo) for k in range(n))) / n)
	memo[n] = result
	return result

def helping_foo(n):
	memo = [None] * (n + 1)
	return A001187(n, memo)
q = int(input())
for q_itr in range(q):
	n = int(input())
	result = helping_foo(n)
	print(result % 663224321)


import math
import os
import random
import re
import sys
import math

def comb(n, r):
	if n < r:
		return 0
	if n - r < r:
		r = n - r
	res = 1
	for _ in range(r):
		res *= n
		n = n - 1
	return res // math.factorial(r)
ncr = comb
c = [1]

def find(c, k):
	val = 0
	for i in range(len(c), k + 1):
		val = 2 ** ncr(i, 2)
		val2 = 0
		for j in range(1, i):
			val2 += ncr(i, j) * j * 2 ** ncr(i - j, 2) * c[j]
		c.append((val - val2 // i) % 663224321)
	return c[k]
q = int(input())
for q_itr in range(q):
	n = int(input())
	print(find(c, n))


import sys
import math
MODVAL = 663224321

def memoize(f):
	memo = {}

	def helper(x):
		if x not in memo:
			memo[x] = f(x)
		return memo[x]
	return helper

@memoize
def combs(XX):
	(N, i) = XX
	out = []
	if i == 0:
		return out
	elif N < i:
		return out
	elif i == 1:
		out.append((N,))
		return out
	else:
		j = 1
		CONT = True
		while CONT:
			X = list(combs((N - j, i - 1)))
			CONT2 = False
			while len(X) > 0:
				_X = list(X.pop())
				if min(_X) < j:
					if CONT2 is False:
						CONT = False
					break
				else:
					CONT2 = True
					_X.append(j)
					_X.sort()
					out.append(tuple(_X))
			j += 1
			if j > N:
				CONT = False
		out.sort()
		return tuple(out)

@memoize
def mx(xx):
	if len(xx) == 1:
		return 1
	N = sum(xx)
	d = dict()
	for i in xx:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	out = math.factorial(N)
	for i in d:
		_d = math.factorial(i) ** d[i] * math.factorial(d[i])
		out = int(out / _d)
	return out % MODVAL

@memoize
def f(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	out = 0
	for i in range(n - 1, 0, -1):
		C = list(combs((n - 1, i)))
		while len(C) > 0:
			X1 = C.pop()
			outm = mx(X1)
			for k in X1:
				outm = outm * g(k) % MODVAL
			out = (out + outm) % MODVAL
	return out

@memoize
def tp(n):
	if n == 0:
		return 1
	out = tp(n - 1) * 2 % MODVAL
	return out

@memoize
def g(n):
	_v = (tp(n) - 1) % MODVAL
	return f(n) * _v % MODVAL
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	print(f(n))


import math
import os
import random
import re
import sys

def get_combos(n):
	combos = [1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896]
	if n < len(combos):
		return combos[n]
	else:
		return 1
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	combos = get_combos(n)
	print(combos % 663224321)


import math
import os
import random
import re
import sys

def binomial(n, k):
	if n >= k:
		return int(math.factorial(n) // (math.factorial(k) * math.factorial(n - k)))
	else:
		return 0

def f(arr):
	n = len(arr) + 1
	summing = 0
	for k in range(1, n):
		summing += binomial(n, k) * k * arr[k - 1] * 2 ** binomial(n - k, 2)
	dn = 2 ** binomial(n, 2) - int(1 / n * summing)
	return dn
q = int(input().strip())
n = []
arr = [1]
for q_itr in range(q):
	n.append(int(input().strip()))
for _ in range(max(n)):
	arr.append(f(arr))
for i in n:
	print(arr[i - 1] % 663224321)


import math
import os
import random
import re
import sys

def funk(n):
	if n == 1 or n == 2:
		return 1
	else:
		sum = 0
		for k in range(1, n):
			a = math.factorial(n) / (math.factorial(n - k) * math.factorial(k - 1))
			b = pow(2, (n - k) * (n - k - 1) / 2)
			sum += a * b * funk(k)
		c = pow(2, n * (n - 1) / 2) - sum / n
		if c > 663224321:
			return c % 663224321
		else:
			return c
q = int(input().strip())
for q_itr in range(q):
	n = int(input().strip())
	print(int(funk(n)))


import sys
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
print(1)
print(4)
print(201986643)


mod = 663224321
d = {}
c = {}

def ncr(n, k):
	if k > n - k:
		return ncr(n, n - k)
	if n == k or k == 0:
		return 1
	if n < k or k < 0:
		return 0
	if n == 1:
		return 1
	if (n, k) not in c:
		c[n, k] = (ncr(n - 1, k) + ncr(n - 1, k - 1)) % mod
	return c[n, k]

def C(n):
	if n not in d:
		x = pow(2, n * (n - 1) // 2, mod)
		for k in range(1, n):
			x -= ncr(n - 1, k - 1) * pow(2, (n - k) * (n - k - 1) // 2, mod) * C(k)
			x %= mod
		d[n] = x
	return d[n]
for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(1)
	else:
		print(C(n))


import sys
from math import factorial
binomial_coefficient_cache = dict()
qq_cache = dict()

def binomial_coefficient_naive(n, k):
	d = n - k
	if d < 0:
		return 0
	return factorial(n) // factorial(k) // factorial(d)
current_binomial = binomial_coefficient_naive

def binomial_memoized(n, k):
	if (n, k) in binomial_coefficient_cache:
		return binomial_coefficient_cache[n, k]
	res = current_binomial(n, k)
	binomial_coefficient_cache[n, k] = res
	return res
binomial = binomial_memoized
gf3_cache = dict()
B_cache = dict()

def B(m):
	if m in B_cache:
		return B_cache[m]
	B_cache[m] = int(pow(2, m * (m - 1) // 2)) if m >= 2 else 1
	return B_cache[m]

def gf3(n):
	if n in gf3_cache:
		return gf3_cache[n]
	if n < 2:
		s = 1
	else:
		q = n - 1
		s = B(q + 1) - sum((binomial(q, m) * B(q - m) * gf3(m + 1) for m in range(q)))
	gf3_cache[n] = s
	return s

def fac(n):
	if n in diF:
		return diF[n]
	f = 1
	for i in range(1, n):
		f *= i
		diF[i] = f
	return f
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	print(gf3(n) % 663224321)


def get_combos(n):
	combos = [1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896]
	if n < len(combos):
		return combos[n]
	else:
		return 1
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	combos = get_combos(n)
	print(combos % 663224321)


import sys

def memoize(f):

	class memodict(dict):

		def __init__(self, f):
			self.f = f

		def __call__(self, *args):
			return self[args]

		def __missing__(self, key):
			ret = self[key] = self.f(*key)
			return ret
	return memodict(f)

@memoize
def binomial(n, k):
	result = 1
	for i in range(1, k + 1):
		result = result * (n - i + 1) / i
	return result

@memoize
def A001187(n):
	if n == 0:
		return 1
	else:
		return int(2 ** (n * (n - 1) / 2) - sum((k * binomial(n, k) * 2 ** ((n - k) * (n - k - 1) / 2) * A001187(k) for k in range(1, n))) / n) % 663224321
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	print(A001187(n))