题目描述

一个由 $1,2,\ldots,N$ 组成的序列

称为一个排列，当且仅当序列中的所有元素两两不同。

如果存在下标

并且满足

则称排列 $p$ 包含一个长度为 $k$ 的递增子序列。

若排列 $p$ 中存在长度为 $B$ 的递增子序列，但不存在长度为 $B+1$ 的递增子序列，则称这个排列的递增度为 $B$。换句话说，排列的递增度就是其最长递增子序列的长度。

给定 $N$ 和 $B$，求递增度恰好为 $B$ 的排列数量。

由于答案可能很大，请输出答案对 $1\,000\,000\,000$ 取模后的结果。

输入格式

一行包含两个整数 $N$ 和 $B$。

输出格式

输出一个整数，表示递增度恰好为 $B$ 的排列数量对 $1\,000\,000\,000$ 取模后的结果。

数据范围

样例

输入

3 2

输出

4

难度参考：CF 2400。