Divide-and-Conquer on a tree is a powerful approach to solving tree problems. 

Imagine a tree, $\boldsymbol{\boldsymbol{t}}$, with $n$ vertices. Let's remove some vertex $\boldsymbol{\nu}$ from tree $\boldsymbol{\boldsymbol{t}}$, splitting $\boldsymbol{\boldsymbol{t}}$ into zero or more connected components, $t_{1},t_{2},\ldots,t_{k}$, with vertices $n_{1},n_{2},\ldots,n_{k}$. We can prove that there is a vertex, $\boldsymbol{\nu}$, such that the size of each formed components is at most $\left\lfloor{\frac{n}{2}}\right\rfloor$.

The Divide-and-Conquer approach can be described as follows:

Initially, there is a tree, $\boldsymbol{\boldsymbol{t}}$, with $n$ vertices.
Find vertex $\boldsymbol{\nu}$ such that, if $\boldsymbol{\nu}$ is removed from the tree, the size of each formed component after removing $\boldsymbol{\nu}$ is at most $\left\lfloor{\frac{n}{2}}\right\rfloor$.
Remove $\boldsymbol{\nu}$ from tree $\boldsymbol{\boldsymbol{t}}$.
Perform this approach recursively for each of the connected components.

We can prove that if we find such a vertex $\boldsymbol{\nu}$ in linear time (e.g., using DFS), the entire approach works in $\mathcal{O}(n\cdot\log n)$. Of course, sometimes there are several such vertices $\boldsymbol{\nu}$ that we can choose on some step, we can take and remove any of them. However, right now we are interested in trees such that at each step there is a unique vertex $\boldsymbol{\nu}$ that we can choose.

Given $n$, count the number of tree $\boldsymbol{\boldsymbol{t}}$'s such that the Divide-and-Conquer approach works determinately on them. As this number can be quite large, your answer must be modulo $m$.

Input Format

A single line of two space-separated positive integers describing the respective values of $n$ (the number of vertices in tree $\boldsymbol{\boldsymbol{t}}$) and $m$ (the modulo value).

Constraints

$1\leq n\leq3000$
$n\lt m\leq10^9$
$m$ is a prime number.

Subtasks

$n\leq9$ for $\textbf{40\%}$ of the maximum score.
$n\leq500$ for $70\%$ of the maximum score. 

Output Format

Print a single integer denoting the number of tree $\boldsymbol{\boldsymbol{t}}$'s such that vertex $\boldsymbol{\nu}$ is unique at each step when applying the Divide-and-Conquer approach, modulo $m$.

Sample Input 0

1 103

Sample Output 0 

1

Explanation 0

For $n=1$, there is only one way to build a tree so we print the value of $1~\text{mod}~103=1$ as our answer.

Sample Input 1

2 103

Sample Output 1

0

Explanation 1

For $n=2$, there is only one way to build a tree:

This tree is not valid because we can choose to remove either node $1$ or node $2$ in the first step. Thus, we print $0$ as no valid tree exists.

Sample Input 2

3 103

Sample Output 2

3 

Explanation 2

For $n=3$, there are $3$ valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red):

Thus, we print the value of $3\:\text{mod}\:103=3$ as our answer.

Sample Input 3

4 103

Sample Output 3

4

Explanation 3

For $n=4$, there are $\begin{array}{c}4\end{array}$ valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red):

The figure below shows an invalid tree with $n=4$:

This tree is not valid because we can choose to remove node $2$ or node $3$ in the first step. Because we had four valid trees, we print the value of $4~\text{mod}~103=4$ as our answer.

Source: hackerrank | Difficulty: HARD
Tags: Dynamic programming


Solutions:
(n, N) = map(int, input().split())

def add(a, b, N=N):
	return (a + b) % N

def mult(a, b, N=N):
	return a * b % N

def div(a, b, N=N):
	return mult(a, pow(b, N - 2, N))

class Cache(object):

	def __init__(self, f, cache_condition=None):
		if cache_condition is None:
			cache_condition = lambda x: True
		self.cache_condition = cache_condition
		self.f = f
		self.d = dict()

	def add(self, *args):
		self.d[args] = self.f(*args)

	def __call__(self, *args):
		if self.cache_condition(args):
			if args not in self.d:
				self.add(*args)
			return self.d[args]
		else:
			return self.f(*args)

	@classmethod
	def cache(cls, cache_condition=None):

		def decorator(f):
			return cls(f, cache_condition)
		return decorator
cache = Cache.cache

class Cache_Generator(Cache):

	def add(self, *args):
		self.d[args] = list(self.f(*args))
cache_generator = Cache_Generator.cache

class Factorial(object):

	def __init__(self, nmax):
		self.data = [0] * nmax
		self.data[0] = 1
		for i in range(1, nmax):
			self.data[i] = mult(self.data[i - 1], i)

	def __call__(self, i):
		return self.data[i]
factorial = Factorial(n)

def n_choose_k(n, k):
	num = factorial(n)
	denom = mult(factorial(n - k), factorial(k))
	return (num, denom)

def combinatorics(n_nodes, partition):
	symmetry_factor = 1
	old_p = None
	count_p = 0
	num = factorial(n_nodes - 1)
	denom = factorial(n_nodes - 1 - sum(partition))
	for p in partition:
		if p == old_p:
			count_p += 1
			symmetry_factor = mult(symmetry_factor, count_p)
		else:
			old_p = p
			count_p = 1
		num = mult(num, ntrees(p))
		denom = mult(denom, factorial(p - 1))
	ret = div(num, mult(denom, symmetry_factor))
	return (ret, symmetry_factor)
top = min(n // 2, 100)

@cache_generator(lambda x: x[0] < top and x[1] < top)
def __partition(sub_tree_max_size, n_nodes):
	yield []
	for i in range(3, min(n_nodes, sub_tree_max_size) + 1):
		for j in _partition(i, n_nodes - i):
			yield ([i] + j)

def _partition(sub_tree_max_size, n_nodes):
	if n_nodes == 0 or sub_tree_max_size == 0:
		yield []
	elif n_nodes == 1:
		yield []
	elif sub_tree_max_size == 1:
		yield []
	else:
		for j in __partition(sub_tree_max_size, n_nodes):
			yield j

def partition(n_nodes):
	return _partition((n_nodes - 1) // 2, n_nodes - 1)

def mylen(x):
	return sum((1 for _ in x))

@cache()
def ntrees(n_nodes):
	if n_nodes == 2:
		return 0
	c = 0
	for p in partition(n_nodes):
		(n, s) = combinatorics(n_nodes, p)
		c = add(c, n)
	return mult(n_nodes, c)
print(ntrees(n))


(n, N) = map(int, input().split())

def add(a, b, N=N):
	return (a + b) % N

def mult(a, b, N=N):
	return a * b % N

def div(a, b, N=N):
	return mult(a, pow(b, N - 2, N))

class Cache(object):

	def __init__(self, f, cache_condition=None):
		if cache_condition is None:
			cache_condition = lambda x: True
		self.cache_condition = cache_condition
		self.f = f
		self.d = dict()

	def add(self, *args):
		self.d[args] = self.f(*args)

	def __call__(self, *args):
		if self.cache_condition(args):
			if args not in self.d:
				self.add(*args)
			return self.d[args]
		else:
			return self.f(*args)

	@classmethod
	def cache(cls, cache_condition=None):

		def decorator(f):
			return cls(f, cache_condition)
		return decorator
cache = Cache.cache

class Cache_Generator(Cache):

	def add(self, *args):
		self.d[args] = list(self.f(*args))
cache_generator = Cache_Generator.cache

class Factorial(object):

	def __init__(self, nmax):
		self.data = [0] * nmax
		self.data[0] = 1
		for i in range(1, nmax):
			self.data[i] = mult(self.data[i - 1], i)

	def __call__(self, i):
		return self.data[i]
factorial = Factorial(n)

def n_choose_k(n, k):
	num = factorial(n)
	denom = mult(factorial(n - k), factorial(k))
	return (num, denom)

def combinatorics(n_nodes, partition):
	symmetry_factor = 1
	old_p = None
	count_p = 0
	num = factorial(n_nodes - 1)
	denom = factorial(n_nodes - 1 - sum(partition))
	for p in partition:
		if p == old_p:
			count_p += 1
			symmetry_factor = mult(symmetry_factor, count_p)
		else:
			old_p = p
			count_p = 1
		num = mult(num, ntrees(p))
		denom = mult(denom, factorial(p - 1))
	ret = div(num, mult(denom, symmetry_factor))
	return (ret, symmetry_factor)
top = min(n // 2, 100)

@cache_generator(lambda x: x[0] < top and x[1] < top)
def __partition(sub_tree_max_size, n_nodes):
	yield []
	for i in range(3, min(n_nodes, sub_tree_max_size) + 1):
		for j in _partition(i, n_nodes - i):
			yield ([i] + j)

def _partition(sub_tree_max_size, n_nodes):
	if n_nodes == 0 or sub_tree_max_size == 0:
		yield []
	elif n_nodes == 1:
		yield []
	elif sub_tree_max_size == 1:
		yield []
	else:
		for j in __partition(sub_tree_max_size, n_nodes):
			yield j

def partition(n_nodes):
	return _partition((n_nodes - 1) // 2, n_nodes - 1)

def mylen(x):
	return sum((1 for _ in x))

@cache()
def ntrees(n_nodes):
	if n_nodes == 2:
		return 0
	c = 0
	for p in partition(n_nodes):
		(n, s) = combinatorics(n_nodes, p)
		c = add(c, n)
	return mult(n_nodes, c)
print(ntrees(n))