题目描述

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

对于一个 $1 \sim n$ 的排列,如果它包含 $t$ 个折点,则称为一个 $t+1$ 单调排列。

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

给定 $n$ 和 $k$,求 $1 \sim n$ 的所有排列中有多少个 $k$ 单调排列。

输入格式

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

输出格式

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

样例

4 2

12

提示

对于 $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$。