Problem Description

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?

Input Format

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

Output Format

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$.

4 2

12

Hint

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