Memory Weaving

Let’s consider a collection of white dragonflies (toys) with wing lengths 1, 2, ..., n. Each dragonfly can open its wings to form any angle \(\theta\) in the open interval \((0, \pi)\). When a dragonfly with wing length \(L\) opens its wings at an angle \(\theta\), the distance between the tips of its two wings is given by the formula \(d=2L\sin(\theta/2)\). Consequently, for any given dragonfly with wing length \(L\), any integer distance \(d\) satisfying
\(1 \le d < 2L\)
can be achieved by a unique choice of \(\theta\) (namely, \(\theta=2\arcsin(d/(2L))\)).

Now, suppose you choose exactly \(m\) dragonflies from the \(n\) available. For each selected dragonfly with wing length \(L\), you choose an integer \(d\) (with \(1 \le d \le 2L-1\)) such that the corresponding opening achieves a distance \(d\), and furthermore, the \(m\) chosen integer distances are all distinct. Two such arrangements (memories) are considered identical if one can reorder the chosen dragonflies such that both the wing lengths and their corresponding distances match exactly.

Your task is to count how many different memories can be woven. Since the answer can be huge, output the result modulo \(p\); that is, compute \(\text{ans}\bmod p\). It can be shown that for a dragonfly with wing length \(L\), there are exactly \(2L-1\) possible integer distances. However, when selecting the \(m\) dragonflies, the chosen distances must be all distinct even though the ranges for different dragonflies may overlap.

Hint: One way to solve this is via dynamic programming. Process the dragonflies (with wing lengths from 1 to \(n\)) one by one. For each dragonfly, if you decide to use it, you would have \((2L-1 - \text{used})\) choices for its distance, where \(\text{used}\) is the number of distances already chosen. Otherwise, you skip it. The answer is the number of valid ways to choose \(m\) pairs \((L, d)\) satisfying for each chosen dragonfly of length \(L\), \(1 \le d \le 2L-1\) and all chosen \(d\)’s are distinct, taken modulo \(p\).

inputFormat

The input consists of a single line containing three space‐separated integers: \(n\), \(m\), and \(p\). Here, \(n\) is the number of white dragonflies, \(m\) is the number of dragonflies you need to choose, and \(p\) is the modulus.

outputFormat

Output a single integer, the number of different memories modulo \(p\).

sample

1 1 100

1