Skwarki Elimination Process

This problem is translated from PA 2018 Round 5 Skwarki.

You are given three integers \(N\), \(K\) and \(P\). Consider all permutations of the set \(\{1,2,\dots,N\}\). For each permutation, define an operation as follows:

• Let the current sequence be \(A_1, A_2, \dots, A_{\ell}\) (initially \(\ell = N\)).
• For an interior element (i.e. \(1 < i A_i\) or \(A_{i+1} > A_i\).
• For the first element, mark \(A_1\) if \(A_2 > A_1\).
• For the last element, mark \(A_\ell\) if \(A_{\ell-1} > A_\ell\).
• Then, remove all marked elements simultaneously to form a new sequence.

Note that an element survives the operation if and only if it is greater than all of its neighbors (if it exists). In other words, after an operation, the remaining sequence consists of the local maxima (with the endpoints considered as having only one neighbor).

The process is repeated until the sequence contains only one element (which is necessarily the global maximum \(N\)). A permutation is considered valid if it takes at least \(K\) operations to reduce the permutation to a single element.

Your task is to compute the number of valid permutations modulo \(P\).

Important: Since the number of valid sequences might be large, output the result modulo \(P\).

inputFormat

The input consists of a single line containing three space-separated integers: \(N\), \(K\) and \(P\).

\(N\): The number of elements in the permutation.\ \(K\): The minimum number of operations required for the elimination process to end with a single element.\ \(P\): The modulus.

outputFormat

Output a single integer representing the number of valid permutations modulo \(P\).

sample

1 1 100

0