P8699 [Lanqiao Cup 2019 National Contest B] Permutation Numbers

In a permutation, a turning point is an element in the permutation that is either smaller than both of its adjacent elements, or larger than both of its adjacent elements. For a permutation of $1 \sim n$, if the permutation contains $t$ turning points, then it is called a $(t + 1)$-monotone permutation. For example, the permutation $(1, 4, 2, 3)$ is a $3$-monotone permutation, where $4$ and $2$ are both turning points. Given $n$ and $k$, how many permutations of $1 \sim n$ are $k$-monotone permutations?

One line contains two integers $n$ and $k$.

Output one integer, representing the answer. The answer may be very large, so you only need to output the remainder when the number of valid permutations is divided by $123456$.

For $20\%$ of the test cases, $1 \leq k \leq n \leq 10$. For $40\%$ of the test cases, $1 \leq k \leq n \leq 20$. For $60\%$ of the test cases, $1 \leq k \leq n \leq 100$. For all test cases, $1 \leq k \leq n \leq 500$. Lanqiao Cup 2019 National Contest, Group B, Problem G. Translated by ChatGPT 5