G. 排列数

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。

对于一个 $1 ∼ n$ 的排列，如果可以将这个排列中包含 $t$ 个折点，则它称为一个 $t+1$ 单调序列。

例如，排列 $(1,4,2,3)$ 是一个 $3$ 单调序列，其中 4 和 2 都是折点。

给定 $n$ 和 $k$ ，请问 $1 ∼ n$ 的所有排列中有多少个 $k$ 单调序列？

输入一行包含两个整数 $n,k$ 。

输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列数量除以 $123456$ 的余数即可。

4 2

对于 $20\%$ 的评测用例， $1 \leq k \leq n \leq 10$ 。

对于 $40\%$ 的评测用例， $1 \leq k \leq n \leq 20$ 。

对于 $60\%$ 的评测用例， $1 \leq k \leq n \leq 100$ 。

对于所有评测用例， $1 \leq k \leq n \leq 500$ 。